#include<cstdio>
#include<cstring>
#include<algorithm>
#define  N  510000
using  namespace  std;
typedef  long  long  LL;
int  bst[N],n;
inline  int  lowbit(int  x){return  x&-x;}
void  ins(int  x)
{
	while(x<=n)
	{
		bst[x]++;
		x+=lowbit(x);
	}
}
int  findans(int  x)
{
	int  ans=0;
	while(x>=1)
	{
		ans+=bst[x];
		x-=lowbit(x);
	}
	return  ans;
}
int  a[N],b[N],c[N];
inline  bool  cmp(int  x,int  y){return  a[x]<a[y];}
int  main()
{
	a[0]=-9999;
	while(1)
	{
		memset(bst,0,sizeof(bst));
		scanf("%d",&n);
		if(n==0)break;
		for(int  i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=i;}
		sort(b+1,b+n+1,cmp);
		int  cnt=0;
		for(int  i=1;i<=n;i++)
		{
			if(a[b[i]]!=a[b[i-1]])cnt++;
			c[b[i]]=cnt;
		}
		LL  ans=0;
		for(int  i=1;i<=n;i++)
		{
			ans+=i-1-findans(c[i]);ins(c[i]);
		}
		printf("%lld\n",ans);
	}
	return  0;
}

#include #include #include #define N 510000 using namespace std; typedef long long LL; int bst[N],n; inline int lowbit(int x){return x&-x;} void ins(int x) { while(x<=n) { bst[x]++; x+=lowbit(x); } } int findans(int x) { int ans=0; while(x>=1) { ans+=bst[x]; x-=lowbit(x); } return ans; } int a[N],b[N],c[N]; inline bool cmp(int x,int y){return a[x]<a[y];} int main() { a[0]=-9999; while(1) { memset(bst,0,sizeof(bst)); scanf("%d",&n); if(n==0)break; for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=i;} sort(b+1,b+n+1,cmp); int cnt=0; for(int i=1;i<=n;i++) { if(a[b[i]]!=a[b[i-1]])cnt++; c[b[i]]=cnt; } LL ans=0; for(int i=1;i<=n;i++) { ans+=i-1-findans(c[i]);ins(c[i]); } printf("%lld\n",ans); } return 0; }

#include<cstdio>
#include<cstring>
#include<algorithm>
#define  N  510000
using  namespace  std;
typedef  long  long  LL;
int  bst[N],n;
inline  int  lowbit(int  x){return  x&-x;}
void  ins(int  x)
{
	while(x<=n)
	{
		bst[x]++;
		x+=lowbit(x);
	}
}
int  findans(int  x)
{
	int  ans=0;
	while(x>=1)
	{
		ans+=bst[x];
		x-=lowbit(x);
	}
	return  ans;
}
int  a[N],b[N],c[N];
inline  bool  cmp(int  x,int  y){return  a[x]<a[y];}
int  main()
{
	a[0]=-9999;
	while(1)
	{
		memset(bst,0,sizeof(bst));
		scanf("%d",&n);
		if(n==0)break;
		for(int  i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=i;}
		sort(b+1,b+n+1,cmp);
		int  cnt=0;
		for(int  i=1;i<=n;i++)
		{
			if(a[b[i]]!=a[b[i-1]])cnt++;
			c[b[i]]=cnt;
		}
		LL  ans=0;
		for(int  i=1;i<=n;i++)
		{
			ans+=i-1-findans(c[i]);ins(c[i]);
		}
		printf("%lld\n",ans);
	}
	return  0;
}

//钟鼎皓

#include <cstdio>
#include <iostream>
#include <string.h>
using namespace std;

const int N=5e5+10;
long long a[N],b[N];
int n;
long long ans;

void Mergesort(int st,int ed)
{
	if(st==ed)return;
	int mid=(st+ed)/2,i=st,j=mid+1,k=st;
	
	Mergesort(st,mid);
	Mergesort(mid+1,ed);
	
	while(i<=mid && j<=ed)
	{
		if(a[i]<=a[j])
		{
			b[k++]=a[i++];
		}
    	else
    	{
    		b[k++]=a[j++];
			ans+=mid-i+1;
		}	
	}
	while(i<=mid)b[k++]=a[i++];
    while(j<=ed)b[k++]=a[j++];
    for(int l=st;l<=ed;l++)
    	a[l]=b[l];
}
int main()
{
    while(scanf("%d",&n) && n!=0)
    {
        ans=0;
		memset(b,0,sizeof(b));
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i]);
        }
        Mergesort(1,n);
        printf("%lld\n",ans);
    }
	return 0;
}

归并排序逆序对