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

/************************************************

┆  ┏┓　　　┏┓ ┆

┆┏┛┻━━━┛┻┓ ┆

┆┃　　　　　　　┃ ┆

┆┃　　　━　　　┃ ┆

┆┃　┳┛　┗┳　┃ ┆

┆┃　　　　　　　┃ ┆

┆┃　　　┻　　　┃ ┆

┆┗━┓　  　┏━┛ ┆

┆　　┃　  　┃　　┆　　　　　　

┆　　┃　  　┗━━━┓ ┆

┆　　┃　 AC代马 　　┣┓┆

┆　　┃　        　　┏┛┆

┆　　┗┓┓┏━┳┓┏┛ ┆

┆　　　┃┫┫　┃┫┫ ┆

┆　　　┗┻┛　┗┻┛ ┆

************************************************ */

//#include<bits/stdc++.h>

#include <stdio.h>

#include <stdlib.h>

#include <cmath>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <queue>

#include <string>

#include <ctype.h>

#include <map>

#include <vector>

#include <set>

using namespace std;

const int maxn=5e5+;

int Tree[maxn],b[maxn];

struct node

{

    int val,pos;

}a[maxn];

bool cmp(node x,node y)

{

    return x.val<y.val;

}

inline int lowbit(int x) //计算2^k

{

    return (x&-x);

}

void add(int x,int value)

{

    for(int i=x; i<maxn; i+=lowbit(i))

            Tree[i]+=value;

}

int get(int x)

{

    int sum=;

    for(int i=x; i>; i-=lowbit(i))

            sum+=Tree[i];

    return sum;

}

int main()

{

    int n;

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

    {

        memset(Tree,,sizeof(Tree));

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

        {

            scanf("%d",&a[i].val);;

            a[i].pos=i;

        }

        sort(a+,a+n+,cmp);

        for(int i=;i<=n;i++) b[a[i].pos]=i;

        long long ans=;

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

        {

            add(b[i],);

            ans+=i-get(b[i]);

        }

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

    }

    return ;

}