Paris_Commune @ 2022-03-30 19:40:52
#include<iostream>
using namespace std;
long long n,a[500005],d[500005],ans=0;
void merge(int s,int t){
if(s==t)return;
int mid=(s+t)/2,i=s,j=mid+1,k=s;
merge(s,mid);
merge(mid+1,t);
for(i=s;i<=mid;i++){
while((a[j]<a[i])&&(j<=t))j++;
ans=ans+(j-mid-1);
}
i=s;j=mid+1;
while(i<=mid&&j<=t){
if(a[i]<a[j])
d[k++]=a[i++];
else d[k++]=a[j++];
}
while(i<=mid)
d[k++]=a[j++];
while(j<=t)
d[k++]=a[j++];
for(int r=s;r<=t;r++){
a[r]=d[r];
}
return;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
merge(1,n);
cout<<ans;
return 0;
}