小朋友排队
time limit per test 2 second memory limit per test 256 megabytes
n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式
　　输入的第一行包含一个整数n，表示小朋友的个数。
　　第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。
输出格式
　　输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
样例输入
3
3 2 1
样例输出
9
样例说明
　　首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。
数据规模和约定
　　对于10%的数据， 1<=n<=10；
　　对于30%的数据， 1<=n<=1000；
　　对于50%的数据， 1<=n<=10000；
　　对于100%的数据，1<=n<=100000，0<=Hi<=1000000

题解

就是求一个数前面有多少个数比它大和后面有多少个数比它小 前面比它大的就是普通的逆序对时求的 后面比它小的要主要当后面全部比它小时也要加上 即在后面while里别忘了加
## 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
import java.io.*;  
import java.util.*;  
public class Main {  
static long count;  
static F[]temp;  
    public static void main(String[] args) throws NumberFormatException, IOException {  
        FastScanner sc=new FastScanner();  
        //Scanner sc=new Scanner(System.in);  
        PrintWriter pw=new PrintWriter(System.out);  
        while(sc.hasNext()){  
            int n=sc.nextInt();  
            F[]shu=new F[n];  
            for(int i=0;i<n;i++){  
                int temp=sc.nextInt();  
                shu[i]=new F(temp,0);  
            }  
            temp=new F[n];  
            count=0;  
            mergeSort(shu,0,n-1);  
            for(int i=0;i<n;i++){  
                long t=shu[i].js;  
                //pw.println(t);  
                //pw.println(shu[i].js+" "+shu1[i].js);  
                //pw.println(shu1[i].num);  
                //pw.println(t);  
                count+=(1+t)*t/2;  
            }  
            pw.println(count);  
            pw.flush();  
        }  
  
    }  
static void mergeSort(F[]shu,int l,int r){  
    if(l<r){  
        int mid=(l+r)/2;  
        mergeSort(shu,l,mid);  
        mergeSort(shu,mid+1,r);  
        merge(shu,l,mid,r);  
    }  
}  
static void merge(F[]shu,int l,int mid,int r){  
    int ll=l;  
    int index=l;  
    int rr=mid+1;  
    long k1=0;  
    long k2=0;  
    while(ll<=mid&&rr<=r){  
        if(shu[ll].num<=shu[rr].num){  
            shu[ll].js+=rr-mid-1;  
            temp[index++]=new F(shu[ll].num,shu[ll].js);  
            ll++;  
        }else{  
            shu[rr].js+=mid-ll+1;  
            temp[index++]=new F(shu[rr].num,shu[rr].js);  
            rr++;  
        }  
    }  
    //count+=(1+k1+k2)*(k1+k2)/2;  
    while(ll<=mid){  
        shu[ll].js+=r-mid;  
        temp[index++]=new F(shu[ll].num,shu[ll].js);  
        ll++;  
    }  
    while(rr<=r){  
        temp[index++]=new F(shu[rr].num,shu[rr].js);  
        rr++;  
    }  
    for(int i=l;i<=r;i++){  
        shu[i]=temp[i];  
    }  
}  
}  
class F{  
    int num;  
    int js;  
    F(int a,int b){  
        num=a;  
        js=b;  
    }  
}