#include using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x M; int A[1010000]; int L[1010000],R[1010000]; ll ret,dif; template class BIT { public: V bit[1<=0;i--) if(tv+bit[ent+(1< bt,bt2; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i], M[A[i]]=0; x=0; ITR(it,M) it->second=++x; FOR(i,N) A[i]=M[A[i]], R[A[i]]++; FOR(i,N) bt2.update(A[i],1); FOR(i,N) { bt2.update(A[i],-1); ret += 1LL*bt.total(A[i]-1)*bt2.total(A[i]-1); ret += 1LL*(i-bt.total(A[i]))*((N-i-1)-bt2.total(A[i])); bt.update(A[i],1); } FOR(i,N) { dif -= L[A[i]]*R[A[i]]; ret -= dif; L[A[i]]++; R[A[i]]--; dif += L[A[i]]*R[A[i]]; } cout<