/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
この問題は E 問題と設定が似ていますが、操作にかかるコストが異なります。
(1,2,\ldots,N) の順列 P があります。P に対して以下の操作を行えます。
- 1 \le i < j \le N を満たす整数 i,j を選ぶ。ただし、i < k < j を満たす全ての整数 k について P_k=k でなければならない。その後、P_i,P_j を入れ替える。
この操作には コストが \boldsymbol{j-i} かかる。
なお、i+1=j の場合、i<k<j を満たす整数 k は存在しないため、操作は常に行えます。したがって、P を昇順にするような操作手順は必ず存在します。
P を昇順にするために必要なコストの和の最小値を求めてください。
制約
- 2 \le N \le 5\times 10^5
- 1 \le P_i \le N
- P は (1,2,\ldots,N) の順列
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
6 6 2 3 5 4 1
出力例 1
6
例えば以下のような手順で 2 回操作をすることでコストの和 6 で P を昇順に並べ替えることができます。
- 1 回目の操作 : i=4, j=5 を選び、P_4, P_5 を入れ替える。コストが 1 かかる。
- 2 回目の操作 : i=1, j=6 を選び、P_1, P_6 を入れ替える。コストが 5 かかる。
6 より小さいコストで昇順にすることはできないため、答えは 6 です。
入力例 2
3 1 2 3
出力例 2
0
必要なコストの和が 0 の場合もあります。
Score : 600 points
Problem Statement
This problem has a similar setting to Problem E, but the cost of the operation is different.
There is a permutation P of (1,2,\ldots,N). You can perform the following operation on P.
- Choose integers i and j satisfying 1 \le i < j \le N. Here, P_k=k must hold for every integer k satisfying i < k < j. Then, swap P_i and P_j.
This operation incurs a cost of \boldsymbol{j-i}.
Note that if i+1=j, there is no integer k satisfying i<k<j, so the operation can always be performed. Therefore, there always exists a sequence of operations that sorts P into ascending order.
Find the minimum total cost required to sort P into ascending order.
Constraints
- 2 \le N \le 5\times 10^5
- 1 \le P_i \le N
- P is a permutation of (1,2,\ldots,N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Output the answer.
Sample Input 1
6 6 2 3 5 4 1
Sample Output 1
6
For example, by performing two operations as follows, P can be sorted into ascending order with a total cost of 6.
- First operation: choose i=4, j=5, and swap P_4, P_5. This costs 1.
- Second operation: choose i=1, j=6, and swap P_1, P_6. This costs 5.
P cannot be sorted into ascending order with a cost less than 6, so the answer is 6.
Sample Input 2
3 1 2 3
Sample Output 2
0
The required total cost can be 0.