玄关

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans=0;
struct node
{
	int x;//原数 
	int id;//在原数组里的编号 
	int t;//离散化之后的数字 
}a[100005];
bool cmp(node x,node y)
{
	return x.x<y.x;
}
bool cmp2(node x,node y)
{
	return x.id<y.id;
}
int t[100005];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int x)
{
    while(pos<=n)
	{
        t[pos]+=x;
        pos+=lowbit(pos);
    }
}
int sum(int pos)
{
    int cnt=0;
    while(pos>0)
	{
        cnt+=t[pos];
        pos-=lowbit(pos);
    }
    return cnt;
}


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x;
		a[i].id=i;
	}
	//----------------------------- 
	sort(a+1,a+1+n,cmp);
	int tot=1;
	for(int i=1;i<=n;)
	{
		int X=a[i].x;
		while(a[i].x==X)
		{
			a[i].t=tot;
			i++;
		}
		tot++;
	}
	sort(a+1,a+1+n,cmp2);
	//--------------------------- 
	for(int i=1;i<=n;i++)
	{
		t[i]=a[i].t;
		add(t[i],1);
		ans+=(i-sum(t[i]));
	}
	cout<<ans;
	return 0;
}