AtCoder Grand Contest 014

F - Strange Sorting


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 2400

問題文

高橋君はソートをするのが大好きです。

そこで、高橋君は 1 から N の順列 (p_1,p_2,...,p_N) を用意し、この順列が (1,2,...,N) になるまで以下の操作を繰り返すことにしました。

  • まず、順列の各 i 項目に対して、1 項目から i 項目までの最大値が i 項目自身であるような項を「高い項」、そうでない項を「低い項」とする。
  • そして、今の順列で並んでいる順に、高い項に現れる数を a_1,a_2,...,a_k 、低い項に現れる数を b_1,b_2,...,b_{N-k} とする。
  • 最後に、順列を (b_1,b_2,...,b_{N-k},a_1,a_2,...,a_k) と並び替える。

さて、高橋君がソートを完了するまでに何回の操作が必要か求めてください。

制約

  • 1 ≦ N ≦ 2×10^5
  • (p_1,p_2,...,p_N)1 から N の順列である。

入力

入力は以下の形式で標準入力から与えられる。

N
p_1 p_2 ... p_N

出力

高橋君がソートを完了するまでにかかる操作の回数を出力せよ。


入力例 1

5
3 5 1 2 4

出力例 1

3

高橋君ははじめ順列 (3,5,1,2,4) を持っており、各操作後、順列は以下のようになる。

  • 1,2 項目が高い項であり、3,4,5 項目が低い項なので、次の順列は (1,2,4,3,5) になる。
  • 1,2,3,5 項目が高い項であり、4 項目が低い項なので、次の順列は (3,1,2,4,5) になる。
  • 1,4,5 項目が高い項であり、2,3 項目が低い項なので、次の順列は (1,2,3,4,5) になる。

入力例 2

5
5 4 3 2 1

出力例 2

4

入力例 3

10
2 10 5 7 3 6 4 9 8 1

出力例 3

6

Score : 2400 points

Problem Statement

Takahashi loves sorting.

He has a permutation (p_1,p_2,...,p_N) of the integers from 1 through N. Now, he will repeat the following operation until the permutation becomes (1,2,...,N):

  • First, we will define high and low elements in the permutation, as follows. The i-th element in the permutation is high if the maximum element between the 1-st and i-th elements, inclusive, is the i-th element itself, and otherwise the i-th element is low.
  • Then, let a_1,a_2,...,a_k be the values of the high elements, and b_1,b_2,...,b_{N-k} be the values of the low elements in the current permutation, in the order they appear in it.
  • Lastly, rearrange the permutation into (b_1,b_2,...,b_{N-k},a_1,a_2,...,a_k).

How many operations are necessary until the permutation is sorted?

Constraints

  • 1 ≤ N ≤ 2×10^5
  • (p_1,p_2,...,p_N) is a permutation of the integers from 1 through N.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_N

Output

Print the number of operations that are necessary until the permutation is sorted.


Sample Input 1

5
3 5 1 2 4

Sample Output 1

3

The initial permutation is (3,5,1,2,4), and each operation changes it as follows:

  • In the first operation, the 1-st and 2-nd elements are high, and the 3-rd, 4-th and 5-th are low. The permutation becomes: (1,2,4,3,5).
  • In the second operation, the 1-st, 2-nd, 3-rd and 5-th elements are high, and the 4-th is low. The permutation becomes: (3,1,2,4,5).
  • In the third operation, the 1-st, 4-th and 5-th elements are high, and the 2-nd and 3-rd and 5-th are low. The permutation becomes: (1,2,3,4,5).

Sample Input 2

5
5 4 3 2 1

Sample Output 2

4

Sample Input 3

10
2 10 5 7 3 6 4 9 8 1

Sample Output 3

6

Submit提出する