https://atcoder.jp/contests/abc318/tasks/abc318_e
$0 \text{-indexed}$ で記述しています。
$i$ と $k$ をfixして考える。一旦 $A[i] \neq A[j]$ の条件を無視する。
愚直に数え上げる方法でとりあえず計算してみる。
$$ \sum_{i=0}^{N-3} \sum_{k=i+2}^{N-1} 1 \, \text {if} \, a[i]=a[k] $$
二重シグマだとステップ回数が $N^2$ になり実行時間に間に合わないので1つのシグマで計算する方法を考える。$k$ をfixしたとき $A[k]$ が $[0,k-2]$ までに何個存在するかが分かればよい。(取りうる $i$ の個数をカウント出来ればよい。)
$k-2$ より前にある $A[k]$ と一致する $A_i$ の添字の集合を $B$ とする。 $|B| = M$ とする。$B$ は取りうる $i$ の集合となる。
$i$ と $k$ をfixして取りうる $j$ の個数ついて考えると $k-i-1$ となる。
これを集合 $B$ 全体で考えると
$$ (k-B_1-1)+(k-B_2-1)+ \dots + (k-B_M-1) $$
となる。これを式変形すると
$$ k \times M - \sum B - M $$
となる。シグマも含めて $k$ をfixして計算式に起こす。
$$ \sum_{k=2}^{N-1} (k-1) \times M - \sum B $$