4012: 计算逆序数
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：477
通过：223
题目描述
给定n个互不相同的整数的序列a1, …, an。如果i<j且ai>aj，则称(ai,aj)是一个逆序。例如，5个数的序列
2, 4, 1, 3, 5
该序列中有3个逆序：(2, 1)、(4, 1)和(4, 3)。
设计一个分治算法计算一个序列中的逆序数。
输入格式
输入包括多组数据。每组数据有两行。每组数据的第一行是一个整数n(100 <= n <= 1000)，n = 0意味着输入结束；第二行包含构成序列的n个整数。
输出格式
对每组测试数据，输出序列中的逆序数。
输入样例 复制
5
2 4 1 3 5
7
2 7 1 4 5 3 9
0
输出样例 复制
3
7