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 in a line, and then N integers N1~Nnfollow, each in a single line. The input is terminated by the number zero.
For case 1, 1<=N<=10, 0<=Ni<=100, the answer <231.
For case 2, 1<=N<=100, 0<=Ni<=106, the answer <231.
For case 3, 1<=N<=106, -231<=Ni<231, the answer <263.
For case 4, 1<=N<=106, -231<=Ni<231, the answer <263.
For each test case, print a number of inversion pairs in the given sequence.