条件を満たす \(3\) つ組を考えるときは、真ん中に着目することが効果的です。今回の問題でも、真ん中の \(j\) を固定したときの答えを考えてみましょう。

\(i<j\) かつ \(A_i=x\) を満たす \(i\) の個数を \(\mathrm{lef}[x]\) 、\(i>j\) かつ \(A_i=x\) を満たす \(i\) の個数を \(\mathrm{rig}[x]\) と置きます。

このとき、\(j\) を固定したときの答えは以下で表されます。

• \(\displaystyle (\sum_{x=1}^N \mathrm{lef}[x] \mathrm{rig}[x]) - \mathrm{lef}[A_j] \mathrm{rig}[A_j]\)

\(j\) を \(2\) から \(N-1\) まで動かしたときの、上式の和が答えとなります。

上式は愚直に毎回計算すると、各回の計算に \(\mathrm{O}(N)\) かかってしまいます。ここで、\( \sum_{x=1}^N \mathrm{lef}[x] \mathrm{rig}[x]\) は \(j\) を \(1\) ずらしてもあまり変化しないことに着目します。

\(j\) を \(1\) ずらしたことによって、\(\mathrm{lef},\mathrm{rig}\) が変化した部分のみ再計算を行うことで、\( \sum_{x=1}^N \mathrm{lef}[x] \mathrm{rig}[x]\) を各 \(j\) について求めることが \(\mathrm{O}(N)\) で出来るようになります。

以上より、全体で \(\mathrm{O}(N)\) でこの問題を解くことができました。