1731: 计算逆序数(2)

给定n个互不相同的整数的序列a₁, …, a_n。如果i<j且a_i>a_j，则称(a_i,a_j)是一个逆序。例如，5个数的序列

2, 4, 1, 3, 5

该序列中有3个逆序：(2, 1)、(4, 1)和(4, 3)。

设计一个分治算法计算一个序列中的逆序数。

输入包括多组数据。每组数据有两行。每组数据的第一行是一个整数n(100 <= n <= 100000)，n = 0意味着输入结束；第二行包含构成序列的n个整数。

对每组测试数据，输出序列中的逆序数。

5
2  4  1  3  5
7
2  7  1  4  5  3  9
0

3
7