Problem Statement

You are given $a permutation P=(P_1,P_2,\cdots,P_N)$ of $(1,2,\cdots,N)$.
You want to perform zero or more swaps of adjacent elements so that P satisfies the following condition:

• The number of indices i such that P_i > P_{i+1} is at most 1.

Find the minimum number of swaps required.

Input

The input is given from Standard Input in the following format:
N
$P_1 P_2 \cdots P_N$

Output

Print the answer.

Constraints

• $2 \leq N \leq 800000$
• $(P_1,P_2,\cdots,P_N)$ is a permutation of $(1,2,\cdots,N)$.
• All input values are integers.

Sample Input 1

3
3 2 1

Sample Output 1

1

Swapping P_1 and P_2 turns P into (2,3,1), which satisfies the condition.

Sample Input 2

4
2 4 1 3

Sample Output 2

0

Sample Input 3

6
2 3 1 6 4 5

Sample Output 3

1

Sample Input 4

20
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

Sample Output 4

36

见题面 Input 部分

见题面 Output 部分