When counting triplets satisfying specific conditions, it is effective to consider the middle element. Let use consider the count when the middle \(j\) is fixed.

Let \(\mathrm{lef}[x]\) be the number of \(i\) with \(i<j\) and \(A_i=x\), and \(\mathrm{rig}[x]\) be the number of \(i\) with \(i>j\) and \(A_i=x\).

Then, the answer for the fixed \(j\) is expressed as follows:

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

The answer is the sum of the expression above over all \(j\) from \(2\) through \((N-1)\).

Naively, evaluating the expression above costs \(\mathrm{O}(N)\) time each. Here, note that \( \sum_{x=1}^N \mathrm{lef}[x] \mathrm{rig}[x]\) does not change so much when \(j\) is incremented by one.

We can compute the delta of \(\mathrm{lef}\) and \(\mathrm{rig}\) when incrementing \(j\) to find \( \sum_{x=1}^N \mathrm{lef}[x] \mathrm{rig}[x]\) for all \(j\) in a total of \(\mathrm{O}(N)\) time.

Therefore, the problem has been solved in a total of \(\mathrm{O}(N)\) time.