\(1\leq j\leq N\) について、\(A_i=j\) をみたす \(i\) \((1\leq i\leq N)\) の個数を \(B_j\) と定義します。

\(1\leq x\leq N\) について、\(1\) 以上 \(N\) 以下の整数の組 \((i,j,k)\) であって、\(A_i,A_j,A_k\) の中に \(x\) がちょうど \(2\) 個含まれるようなものの数を \(C_x\) とすると、ある \((i,j,k)\) が \(2\) つ以上の \(x\) について条件をみたすことはないため、求める答えは \((C_1+C_2+\cdots+C_N)\) です。
一方で、条件をみたす \((i,j,k)\) は、\(A_{i'}=A_{j'}=x\) \((1\leq i'<j'\leq N)\) をみたすような \((i',j')\) と \(A_{k'}\neq x\) \((1\leq k'\leq N)\)をみたす \(k'\) の組み合わせと一対一に対応します。よって、\(C_x=\frac{B_x(B_x-1)}{2}\times (N-B_x)\) となります。

ゆえに、求める値は \(\displaystyle\sum_{i=1}^N \frac{B_i(B_i-1)}{2}\times (N-B_i)\) となります。
\((B_1,B_2,\ldots,B_N)\) は入力から \(O(N)\) で求めることができ、それらから \(O(N)\) で答えを求めることができるため、全体で \(O(N)\) であり、十分高速です。

c++ による実装例:

#include <bits/stdc++.h>
using namespace std;

#define N (int)2e+5

int main(void){
	int n,x;
	long long a[N]={};
	long long ans=0;

	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x;
		a[x-1]++;
	}
	for(int i=0;i<n;i++){
		ans+=a[i]*(a[i]-1)*(n-a[i])/2;
	}
	cout<<ans<<endl;
	return 0;
}