本道题的目的其实就是求逆序数的个数,这里使用归并实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out=new PrintWriter(System.out);
static StringTokenizer st=null;
static int[] arr;
static int next()throws IOException{
while(st==null||!st.hasMoreTokens())
st=new StringTokenizer(in.readLine());
return Integer.parseInt(st.nextToken());
}
static long mergeSort(int[] arr,int left,int right){
if(left>=right)
return 0;
int mid=left+right>>1;
long ans = mergeSort (arr,left,mid) + mergeSort (arr,mid + 1,right);
int i=left;
int j=mid+1;
int k=0;
int[] tmp = new int[right-left+1];
while(i<=mid&&j<=right){
if(arr[i]<=arr[j]){
tmp[k++]=arr[i++];
}
else{
tmp[k++]=arr[j++];
ans += mid - i + 1;
}
}
while(i<=mid){
tmp[k++]=arr[i++];
}
while(j<=right){
tmp[k++]=arr[j++];
}
for(i=left,j=0;i<=right;i++,j++){
arr[i]=tmp[j];
}
return ans;
}
public static void main(String[] args) throws IOException{
int n=next();
while(n!=0){
arr=new int[n+1];
for(int i=0;i<n;i++){
arr[i]=next();
}
long res=mergeSort(arr, 0, n-1);
out.println(res);
n=next();
}
out.flush();
}
}