Contest Duration: - (local time) (300 minutes) Back to Home
D - Almost Bubble Sort /

Time Limit: 10 sec / Memory Limit: 2048 MB

### 問題文

(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます．

• P_i > P_{i+1} を満たす i の個数は高々 1 つである．

### 制約

• 2 \leq N \leq 800000
• (P_1,P_2,\cdots,P_N)(1,2,\cdots,N) の順列
• 入力される値はすべて整数

### 入力

N
P_1 P_2 \cdots P_N


### 入力例 1

3
3 2 1


### 出力例 1

1


P_1P_2 を swap することで P=(2,3,1) になり，P は条件を満たします．

### 入力例 2

4
2 4 1 3


### 出力例 2

0


### 入力例 3

6
2 3 1 6 4 5


### 出力例 3

1


### 入力例 4

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


### 出力例 4

36


Score : 2000 points

### 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.

### 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.

### Input

The input is given from Standard Input in the following format:

N
P_1 P_2 \cdots P_N


### 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