# 题目

## 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

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.

## Output

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

# 代码

```/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！

*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 500005;
int a[maxn];

long long ans;

//将已经排好序的a[l]~a[mid] a[mid+1]~a[r]拼合起来
void merge(int a[],int l,int mid,int r) {
int pos1 = l;//左侧的指针
int pos2 = mid + 1;//右侧的指针
int *temp = new int[r - l + 1];
int pos = 0;//临时数组的指针
while(pos1 <= mid || pos2 <= r) {
if(pos1 > mid) {
temp[pos++] = a[pos2++];
}
if(pos2 > r) {
temp[pos++] = a[pos1++];
}
if(pos1 <= mid&&pos2 <= r) {
if(a[pos1] <= a[pos2]) {
temp[pos++] = a[pos1++];
} else {
temp[pos++] = a[pos2++];
ans += mid - pos1 + 1;//交换
}
}
}
for(int i = 0;i <= r - l;i++)
a[l + i] = temp[i];
}

//归并排序 对a[l]~a[r]排序
void mergesort(int a[],int l,int r) {
if(l<r) {
int mid = (l + r) / 2;
mergesort(a,l,mid);
mergesort(a,mid + 1,r);
merge(a,l,mid,r);
}
}

bool Do() {
int n;
if(scanf("%d",&n),n == 0)
return false;

REP(n)
scanf("%d",&a[o]);

ans = 0;
mergesort(a,0,n - 1);
printf("%lld\n",ans);
/*REP(n)
printf("%d ",a[o]);
printf("\n");*/

return true;
}

int main() {
while(Do());
return 0;
}
```