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>
using namespace std;

#define CO const
#define IN inline
typedef long long int64;

template<class T> IN T read(){
	T x=0,w=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*w;
}
template<class T> IN T read(T&x){
	return x=read<T>();
}

CO int N=2e5+10;
namespace treap{
	int ch[N][2],pri[N],tot;
	int val[N],mn[N],mx[N];
	
	IN int new_node(int v){
		int x=++tot;
		pri[x]=rand()^rand()<<15,val[x]=mn[x]=mx[x]=v;
		return x;
	}
	IN void push_up(int x){
		mn[x]=ch[x][0]?mn[ch[x][0]]:val[x];
		mx[x]=ch[x][1]?mx[ch[x][1]]:val[x];
	}
	int merge(int x,int y){
		if(!x or !y) return x+y;
		if(pri[x]>pri[y]){
			ch[x][1]=merge(ch[x][1],y);
			return push_up(x),x;
		}
		else{
			ch[y][0]=merge(x,ch[y][0]);
			return push_up(y),y;
		}
	}
	void split(int x,int v,int&l,int&r){
		if(!x) {l=r=0; return;}
		if(val[x]<=v)
			l=x,split(ch[l][1],v,ch[l][1],r),push_up(l);
		else
			r=x,split(ch[r][0],v,l,ch[r][0]),push_up(r);
	}
	IN void push_back(int&x,int v){
		x=merge(x,new_node(v));
	}
	IN void pop_back(int&x,int v){
		split(x,v-1,x,*new int);
	}
}

int a[N],q[2*N];

int main(){
	srand(20030506);
	int n=read<int>();
	for(int i=1;i<=n;++i) read(a[i]);
	
	int L=1,R=0;
	for(int i=1;i<=n;++i){
		if(i==1 or a[i-1]>a[i]) ++R; // divide the permutation into monotone segments
		treap::push_back(q[R],a[i]);
	}
	int last=n; // consecutive elements in the end removable
	for(;last and treap::mx[q[R]]==last;--last)
		treap::pop_back(q[R],last);
	
	int ans=0;
	while(last){
		++ans;
		for(;L<R and !q[L];++L); // skip empty segments
		int x=q[L],mx=treap::mx[x]; // all elements in the first segment are high
		for(int i=++L;i<=R and mx!=last;++i)if(q[i]){
			if(treap::mx[q[i]]<mx) continue;
			int l,r;treap::split(q[i],mx,l,r);
			q[i]=l,x=treap::merge(x,r),mx=treap::mx[x];
			if(q[i-1] and treap::mx[q[i-1]]<treap::mn[q[i]]) // merge segments
				q[i]=treap::merge(q[i-1],q[i]),q[i-1]=0;
		}
		if(q[R] and treap::mx[q[R]]<treap::mn[x])
			x=treap::merge(q[R],x),q[R]=0;
		q[++R]=x;
		for(;last and treap::mx[q[R]]==last;--last)
			treap::pop_back(q[R],last);
	}
	printf("%d\n",ans);
	return 0;
}