D - Almost Bubble Sort Editorial /

Time Limit: 10 sec / Memory Limit: 2048 MB

配点 : 2000 点

問題文

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

隣接要素の swap を 0 回以上行って，P が以下の条件を満たすようにしたいです．

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

必要な swap の最小回数を求めてください．

制約

  • 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_1 と P_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

Output

Print the answer.

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