#include<cstdio>
#define in inline
#define re register
#define int long long
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
int n,a[510000],d[510000],ans;
void msort(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
msort(l,mid);
msort(mid+1,r);
re int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) d[k++]=a[i++];
else d[k++]=a[j++],ans+=mid-i+1;
//左半区间和右半区间为两个子问题, 两个区间之内的逆序对已求出, 现在合并两区间, 只要考虑跨区间的逆序对
//当a[j]>a[i]时, a[i~mid]区间内每一个数与a[j]构成一个逆序对
}
while(i<=mid) d[k++]=a[i++];
while(j<=r) d[k++]=a[j++];
for(i=l;i<=r;++i) a[i]=d[i];
}
signed main()
{
while(1)
{
n=read();
if(!n) break;
for(re int i=1;i<=n;++i) a[i]=read();
msort(1,n);
printf("%lld\n",ans);
ans=0;
}
return 0;
}
最新评论