Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is
sorted in ascending order. For the input sequence 

9 1 0 5 4 ,


Ultra-QuickSort produces the output 

0 1 4 5 9 .


Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

Output

Sample Input

5

9

1

0

5

4

3

1

2

3

0

Sample Output

6

0

//32684K	1579MS

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define M 500007

#define ll __int64

using namespace std;

int s[M],n;

struct Tree

{

    int l,r,mid;

    ll val;

}tree[M<<1];

struct sa

{

    int id;

    ll val;

}p[M*2];

int cmp(sa a,sa b)

{

    return a.val>b.val;

}

void build(int left,int right,int i)

{

    tree[i].l=left;tree[i].r=right;tree[i].mid=(left+right)>>1;tree[i].val=0;

    if(left==right){return;}

    build(left,tree[i].mid,i*2);

    build(tree[i].mid+1,right,i*2+1);

}

int query(int x,int i)

{

    if(tree[i].l==tree[i].r)return tree[i].val;

    if(x<=tree[i].mid)return query(x,i*2)+tree[i].val;

    else return query(x,i*2+1)+tree[i].val;

}

void insert(int left,int right,int i)

{

    if(tree[i].l==left&&tree[i].r==right){tree[i].val++;return;}

    if(right<=tree[i].mid)insert(left,right,2*i);

    else if(left>tree[i].mid)insert(left,right,2*i+1);

    else {insert(left,tree[i].mid,i*2);insert(tree[i].mid+1,right,i*2+1);}

}

void discretization()

{

    int tmp=p[1].val,pos=1;

    for(int i=1;i<=n;i++)

        if(p[i].val!=tmp)p[i].val=++pos,tmp=p[i].val;

        else p[i].val=pos;

    for(int i=1;i<=n;i++)

        s[p[i].id]=p[i].val;

}

int main()

{

    while(scanf("%d",&n)&&n)

    {

        ll ans=0;

        build(0,M,1);

        memset(s,0,sizeof(s));

        for(int i=1;i<=n;i++)

        {

            scanf("%I64d",&p[i].val);

            p[i].id=i;

        }

        sort(p+1,p+n+1,cmp);

        discretization();

        for(int i=1;i<=n;i++)

            printf("%d ",s[i]);

        printf("\n");

        for(int i=1;i<=n;i++)

        {

                ans+=query(s[i],1);

                insert(s[i],M,1);

        }

        printf("%I64d\n",ans);

    }

    return 0;

}