1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 int n,m; 5 const int N=100005; 6 ll cnt[N],arr[N],brr[N]; 7 vector<ll> vec; 8 int getid(ll x) { return lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1; } 9 int lowbits(int x) { return x&-x; } 10 void add(int x,int value){ while(x<=N) cnt[x]+=value,x+=lowbits(x); } 11 int query(int x){ 12 int sum=0; 13 while(x>0){ sum+=cnt[x],x-=lowbits(x); } 14 return sum; 15 } 16 int main(){ 17 scanf("%d",&n); 18 for(int i=1;i<=n;i++) scanf("%lld",&arr[i]),vec.push_back(arr[i]); 19 sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end()); 20 ll sum=0; 21 for(int i=1;i<=n;i++){ 22 add(getid(arr[i]),1); 23 brr[i]+=i-query(getid(arr[i])); //i-小于等于的它的个数就是前面大于它的个数 24 } 25 // memset(brr,0,sizeof(brr)); 26 memset(cnt,0,sizeof(cnt)); 27 for(int i=n;i>=1;i--){ 28 add(getid(arr[i]),1); 29 brr[i]+=query(getid(arr[i])-1); //后面小于它的个数 30 // cout << brr[i] << endl; 31 } 32 for(int i=1;i<=n;i++){ 33 sum+=1LL*(1+brr[i])*brr[i]/2; 34 } 35 cout << sum << endl; 36 return 0; 37 }