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