You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

For each case, output the minimum times need to sort it in ascending order on a single line.

3
1 2 3
4 
4 3 2 1 

0
6

题目大意：给你一个1-n的全排列，只能相连的两两交换位置。问最小交换多少次才使这个序列成为单调递增序列。
分析：其实交换的目的就是把下标小且数值大的移到下标大的位置。因为只能相连的两两交换位置，不难便看出，移动最小次数就是：逆序对数（就是当前下标的数值大于比当前下标大的下标的数值，有点绕...）比如 4 3 2 1 ,4>3,4下标小于3的下标。所以4,3是一对逆序数。同理，(4,2)(4,1)(3,2)(3,1)(2,1)都是逆序数，共6个。所以此题转化为求一个序列逆序数问题。树状数组可解决。（且不用离散化）。另外归并排序也可以。。。上树状数组AC代码。
//如果得出交换最小次数就是 这个数列的逆序数 就好做了
//因为题目给出的序列就是1-n的排列。所以不需要离散化。
#include<stdio.h>
#include<string.h>
int c[1001];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void updata(int x,int d)
{
    while(x<=n)
    {
        c[x]=c[x]+d;
        x=x+lowbit(x);
    }
}
int getsum(int x)
{
    int res = 0;
    while(x>0)
    {
        res=res+c[x];
        x=x-lowbit(x);
    }
    return res;
}
int main()
{
    int i;
    int a;
    int ans;
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        ans=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a);
            updata(a,1);
	//当前输入的逆序数就是getsum(n)-getsum(a)这点不好理解，仔细调试就应该明白了。
            ans=ans+(getsum(n)-getsum(a));
        }
        printf("%d\n",ans);
    }
    return 0;
}