In a number sequence S = {S1, S2, S3, …, Sn}, we called (i,j) an “inversion pair” when Si > Sj and i < j. Given S, calculate the number of inversion pair in this sequence.
Case1: 1<=N<=10^2
Case2: 1<=N<=10^3
Case3: 1<=N<=10^5
Case4: 1<=N<=10^6
There are several numbers of test cases. Each case begins with an integer N (1 <= N <= 10^6) in a line, and then N integers(each number fits in 64-bit integer) follow, in a single line. The input is terminated by the number zero.
For each test case, print a number of inversion pairs in the given sequence. All the answer can be fit in 64-bits integers.