E - Gap Swap (hard) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 900 点

問題文

この問題は D 問題と設定が似ていますが、操作にかかるコストが異なります。

(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{1} かかる。

なお、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

2

例えば以下のような手順で 2 回操作をすることでコストの和 2 で P を昇順に並べ替えることができます。

  • 1 回目の操作 : i=4, j=5 を選び、P_4, P_5 を入れ替える。コストが 1 かかる。
  • 2 回目の操作 : i=1, j=6 を選び、P_1, P_6 を入れ替える。コストが 1 かかる。

2 より小さいコストで昇順にすることはできないため、答えは 2 です。

入力例 2

3
1 2 3

出力例 2

0

必要なコストの和が 0 の場合もあります。

Score : 900 points

Problem Statement

This problem has a similar setting to Problem D, 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{1}.

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

2

For example, by performing two operations as follows, P can be sorted into ascending order with a total cost of 2.

  • 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 1.

P cannot be sorted into ascending order with a cost less than 2, so the answer is 2.

Sample Input 2

3
1 2 3

Sample Output 2

0

The required total cost can be 0.