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.

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

5

9

1

0

5

4

3

1

2

3

0

6

0

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<map>

const int maxn=5e5+;

typedef long long ll;

using namespace std;

struct node

{

    ll l,r;

    ll sum;

}tree[maxn<<];

int a[maxn],sub[maxn],cnt;

void pushup(int m)

{

    tree[m].sum=(tree[m<<].sum+tree[m<<|].sum);

}

//void pushdown(int  m)

//{

//    if(tree[m].lazy)

//    {

//        tree[m<<1].lazy=tree[m].lazy;

//        tree[m<<1|1].lazy=tree[m].lazy;

//        tree[m<<1].sum=tree[m].lazy*(tree[m<<1].r-tree[m<<1].l+1);

//        tree[m<<1|1].sum=tree[m].lazy*(tree[m<<1|1].r-tree[m<<1|1].l+1);

//        tree[m].lazy=0;

//    }

//    return ;

//}

void build(int m,int l,int r)

{

    tree[m].l=l;

    tree[m].r=r;

    tree[m].sum=;

    if(l==r)

    {

        tree[m].sum=;

        return ;

    }

    int mid=(tree[m].l+tree[m].r)>>;

    build(m<<,l,mid);

    build(m<<|,mid+,r);

    pushup(m);

    return ;

}

void update(int m,int index ,int  val)

{

    if(tree[m].l==index&&tree[m].l==tree[m].r)

    {

        tree[m].sum++;

        return ;

    }

    int mid=(tree[m].l+tree[m].r)>>;

    if(index<=mid)

    {

        update(m<<,index,val);

    }

    else

    {

        update(m<<|,index,val);

    }

    pushup(m);

    return ;

}

ll query(int m,int l,int r)

{

    if(l>r)

    {

        return ;

    }

    if(tree[m].l==l&&tree[m].r==r)

    {

        return tree[m].sum;

    }

//    pushdown(m);

    int mid=(tree[m].l+tree[m].r)>>;

    if(r<=mid)

    {

        return query(m<<,l,r);

    }

    else if(l>mid)

    {

        return query(m<<|,l,r);

    }

    else

    {

        return query(m<<,l,mid)+query(m<<|,mid+,r);

    }

}

int main()

{

   int n;

   while(cin>>n)

   {

       if(n==)

       {

           break;

    }

    for(int i=;i<n;++i)scanf("%d",&sub[i]),a[i]=sub[i];

    sort(sub,sub+n);

    int size=unique(sub,sub+n)-sub;

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

    a[i]=lower_bound(sub,sub+size,a[i])-sub+;

    build(,,size);

    ll sum=;

    for(int t=;t<n;t++)

    {

        sum+=query(,a[t]+,size);

        update(,a[t],);

    }

    printf("%lld\n",sum);

   }

   return ;

}