用归并排序的思想，每次进行归并的时候右边组的数小于左边组的数，那么右边较小的这个数一定小于左边组内剩余的数，因此ans += mid - i + 1;其中(mid - i + 1)表示左边组内剩余的数量，累计答案ans直到最后排序完成即为答案。

#include<bits/stdc++.h>

using namespace std;

const int N = 500011;

int n;
long long ans = 0;
long long a[N] = {0};

void merge_sort(long long l, long long r){
    
    if(l >= r) return ;
    long long mid = (l + r) >> 1;
    long long i = l, j = mid + 1;
    int b[N], k = 0;
    
    merge_sort(i, mid);
    merge_sort(j, r);
    
    while(i <= mid && j <= r){
        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 <= r) b[k++] = a[j++];
    
    for(int i=l,k=0;i<=r;) a[i++] = b[k++];
    
}

int main(){
    
    do{
        ans = 0;
        scanf("%d",&n);
        if(!n)continue;
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        
        merge_sort(0, n - 1);
        
        printf("%lld\n",ans);
    }while(n);
    return 0;
}