/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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