Sort
time limit per test 2 second memory limit per test 256 megabytes
You want to process a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order.

传送门：EOJ3234

Input

There are several test cases, please process till EOF. For each test case, the first line contains integer n (1≤n≤10^5). The second line contains n space-separated integers a1,a2,…,an (1≤ai≤10^9).

Output

For each test case, output the minimum times of swapping in one line.

Sample Input

1
2
2
1 2

Sample Output

1
0

题解

典型求逆序对问题 此处要注意当数组元素个数很大时,逆序对的数量会很大,此时需要long来存储
## AC code:(不包含输入类) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.io.*;  
import java.util.*;  
public class Main {  
    static long count;  
    static int[]temp;  
    static int[]shu;  
    public static void main(String[] args) {  
        FastScanner sc = new FastScanner();  
        PrintWriter pw = new PrintWriter(System.out);  
        //int t=sc.nextInt();  
        int k=0;  
        while (sc.hasNext()) {  
            k++;  
            int n=sc.nextInt();  
            shu=new int[n];  
            temp=new int[n];  
            count=0;  
            for(int i=0;i<n;i++)shu[i]=sc.nextInt();  
            mergeSort(shu,0,n-1);  
            //pw.printf("Scenario #"+k+":\n");  
            pw.printf("%d\n",count);  
            pw.flush();  
        }  
    }  
    static void mergeSort(int[]shu,int left,int right){  
        if(left<right){  
            int mid=(left+right)/2;  
            mergeSort(shu,left,mid);  
            mergeSort(shu,mid+1,right);  
            merge(shu,left,mid,right);  
        }  
    }  
    /*static void merge(int[]input,int left,int center,int right){ 
        int []tempArray = new int[right-left+1]; 
        int mid = center+1; 
        int temp = left; 
        int current = 0; 
        while(left<=center && mid<=right){ 
            if(input[left]>input[mid]){ 
                tempArray[current++]=input[mid++];         
                count+=center-left+1; 
            }else{ 
                tempArray[current++]=input[left++]; 
            } 
        } 
        while(left<=center){ 
            tempArray[current++]=input[left++]; 
        } 
        while(mid<=right){ 
            tempArray[current++]=input[mid++]; 
        } 
        current=0; 
        while(temp<=right){ 
            input[temp++]=tempArray[current++]; 
        } 
    } 
    */static void merge(int[]shu,int left,int mid,int right){  
        int k=left;  
        int a=left;  
        int b=mid+1;  
        while(a<=mid&&b<=right){  
            if(shu[a]>shu[b]){  
                temp[k++]=shu[b++];  
                count+=mid-a+1;  
            }else{  
                temp[k++]=shu[a++];  
            }  
        }  
        while(a<=mid){  
            temp[k++]=shu[a++];  
        }  
        while(b<=right){  
            temp[k++]=shu[b++];  
        }  
        for(int i=left;i<=right;i++){  
            shu[i]=temp[i];  
        }  
    }  
    /*static void merge(int[]shu,int l,int m,int r) 
    { 
        int i = l; 
        int j = m + 1; 
        int k = l; 
        while(i <= m && j <= r) 
        { 
            if(shu[i] > shu[j]) 
            { 
                temp[k++] = shu[j++]; 
                count += m - i + 1; 
            } 
            else 
            { 
                temp[k++] = shu[i++]; 
            } 
        } 
        while(i <= m) temp[k++] = shu[i++]; 
        while(j <= r) temp[k++] = shu[j++]; 
        for(int q=l;q<=r;q++) 
            shu[q] = temp[q]; 
    }*/  
}