看一个数对答案的贡献，就是找他前面有多少比它小的，后面有多少比他大的，一乘，就是他前后有多少涉及到他的顺序对，就是他对答案的贡献。
因为n<=300000，效率N*log(N)能过，也就是树状数组。离散一下权值，用权值作为数组下标。
维护两个，一个是之前最小，正推，每推一个，压进当前位。另一个反推，找到比自己小的，做减法即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}return sum*f;
}
int n,a[300205],h[300205],sz;
ll ans=0;
int t1[300205],t2[300205],v1[300205],v2[300205];
int lowbit(int x){return x&(-x);}
void add1(int x,int k)
{for(int i=x;i<=n;i+=lowbit(i))t1[i]+=k;
}
void add2(int x,int k)
{for(int i=x;i<=n;i+=lowbit(i))t2[i]+=k;
}
ll q1(int x)
{int s=0;while(x>0){s+=t1[x],x-=lowbit(x);}return s;
}
ll q2(int x)
{int s=0;while(x>0){s+=t2[x],x-=lowbit(x);}return s;
}
int main()
{//freopen("calc.in","r",stdin);//freopen("calc.out","w",stdout);n=read();for(int i=1;i<=n;i++)h[i]=a[i]=read();sort(h+1,h+n+1);for(int i=1;i<=n;i++)a[i]=lower_bound(h+1,h+n+1,a[i])-h;for(int i=1;i<=n;i++){v1[i]=q1(a[i]-1);add1(a[i],1);}for(int i=n;i>=1;i--){int k=n-i;v2[i]=k-q2(a[i]);add2(a[i],1);}for(int i=1;i<=n;i++)ans+=v1[i]*v2[i];printf("%lld\n",ans);
}