For \(1\leq j\leq N\), let \(B_j\) be the number of integers \(i\) \((1\leq i\leq N)\) with \(A_i=j\).

For \(1\leq x\leq N\), define \(C_x\) as the number of triples \((i,j,k)\) of integers such that exactly two of \(A_i,A_j\) and \(A_k\) equal \(x\). Then no \((i,j,k)\) satisfies the condition for different \(x\), so the sought answer is \((C_1+C_2+\cdots+C_N)\).
Here, any triple \((i,j,k)\) satisfying the condition corresponds one-by-one to a combination of \((i',j')\) such that \(A_{i'}=A_{j'}=x\) \((1\leq i'<j'\leq N)\) and \(k'\) such that \(A_{k'}\neq x\) \((1\leq k'\leq N)\). Hence, \(C_x=\frac{B_x(B_x-1)}{2}\times (N-B_x)\).

Therefore, the sought value is \(\displaystyle\sum_{i=1}^N \frac{B_i(B_i-1)}{2}\times (N-B_i)\).
\((B_1,B_2,\ldots,B_N)\) can be found in \(O(N)\) time from the input, and the answer can be calculated in \(O(N)\), so the total cost is \(O(N)\), which is fast enough.

Sample code in 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;
}