Maija is sorting her book shelf by the books' ID numbers. She keeps repeating the same operation until the shelf is sorted: she picks two adjacent books where the left one's ID is greater than the right one's and swaps them. It can be proven that the books will be sorted after a finite number of moves like this. Calculate the minimum number of moves it takes to sort $n$ books when the $i$-th one's ID is $a_i$.

Input

The first line contains an integer $n$. The second line contains $n$ integers $a_1,\,a_2,\ldots,\,a_n$.

Output

Print the minimum number of moves required to sort the books.

Constraints

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq a_i \leq 10^9$

Example 1

Input:

5
6 1 8 9 3

Output:

4

Example 2

Input:

10
6 1 8 9 3 2 6 6 9 5

Output:

18

Example 3

Input:

1
1000000000

Output:

0