Given a 0-indexed array A of n integers we define an inversion as a pair of integers (i, j) such that 0 <= i < j < n and A[i] >A[j].

In this problem, you will be given an array and your task is to calculate the total number of inversions in this array.

Input

The input consists of several test cases.

Each test case is described in two lines. The first line contains n, the size of the array (1 <= n <= 1000). The second line contains the array: n integers separated by one or more spaces. Each integer in the array will be between -10⁹ and 10⁹, inclusive.

Output

For each test case, write the total number of inversions of the array on a single line.

Example

Input:
2
1 2
3
3 2 1
4
0 0 0 0
5
1 2 3 5 4
6
3 1 6 5 2 4
10
5 2 10 8 1 9 4 3 6 7
0

Output:
0
3
0
1
7
22