\(T_i\) を \(A\) の中に含まれる \(i\) の個数と定義します。すると、求める値は \(\displaystyle\sum_{1\le i<j<k\le \text{inf}}T_iT_jT_k\) と書くことができます。ここで、 \(\text{inf}\) は \(A\) の最大値、つまり \(2\times 10^5\) です。

上の式の \(k\) を全探索することを考えます。 なので、 \(k=1,2,\ldots,N\) に対し \(\displaystyle\sum_{1\le i<j<k}T_iT_j\) を高速に求めることを考えます。

\(\displaystyle\sum_{1\le i<j<k}T_iT_j=\frac12\left(\sum_{i=1}^{k-1}T_i\right)^2-\frac12\sum_{i=1}^{k-1}T_i^2\) です。これより、 \(\displaystyle X_j=\sum_{i=1}^j T_i\) 、 \(\displaystyle Y_j=\sum_{i=1}^j T_i^2\) と定義して \(O(\text{inf})\) で前計算することにより 各 \(k\) に対し\(\displaystyle\sum_{1\le i<j<k}T_iT_j\) が \(O(1)\) で求めることができます。

以上でこの問題が解けました。計算量は \(O(N+\max A)\) です。

実装例(Java)