Problem: 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.

Examples

Input

5
3 5 1 2 4


Output

3


Input

5
5 4 3 2 1


Output

4


Input

10
2 10 5 7 3 6 4 9 8 1


Output

6

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;

typedef long long ll;
typedef pair<int,int> PA;

const int MAX_N=2e5;

int N,P[MAX_N];

int inx[MAX_N];

int main(){
	cin>>N;
	REP(i,N){
		cin>>P[i];
		P[i]--;
	}
	REP(i,N){
		inx[P[i]]=i;
	}
	int ans=0,f;
	REP(i,N-1){
		int j=N-2-i;
		if (ans==0){
			if (inx[j]>inx[j+1]){
				ans++;
				f=j+1;
			}
		}else{
			vector<PA> vec(3);
			vec[0]=PA(inx[j],j);
			vec[1]=PA(inx[j+1],j+1);
			vec[2]=PA(inx[f],f);
			sort(vec.begin(),vec.end());
			bool flg=false;
			REP(k,3){
				if (vec[k].second==j && vec[(k+1)%3].second==j+1){
					flg=true;
				}
			}
			if (!flg){
				ans++;
				f=j+1;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}