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.
There are several numbers of test cases. Each case begins with an integer N (1 <= N <= 106) in a line, and then N integers follow, each 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.