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 FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
using vi=vector<int>;
#define PB push_back
#define ALL(x) x.begin(),x.end()
//#define LN cerr<<__LINE__<<endl
#define LN 0
using pi=pair<int,int>;
int read(){
	int i;
	scanf("%d",&i);
	return i;
}
void chmin(int&a,int b){
	a=a<b?a:b;
}
void chmax(int&a,int b){
	a=a>b?a:b;
}
struct SegTree{
	vi buf;
	int s;
	SegTree(int n){
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2,-1);
	}
	void Update(int i,int v){
		i+=s;
		buf[i]=v;
		while((i/=2)>=1)buf[i]=max(buf[i*2],buf[i*2+1]);
	}
	int GetIdx(int b,int e,int t,vi&dst,int l,int r,int i){
		if(buf[i]<=t||e<=l||r<=b)return t;
		if(b<=l&&r<=e){
			if(l+1==r){
				if(t<buf[i])dst.PB(l);
				return max(t,buf[i]);
			}else{
				if(t<buf[i*2])
					t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
				if(t<buf[i*2+1])
					t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
				return t;
			}
		}
		t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
		t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
		return t;
	}
	void GetIdx(int b,int e,vi& dst){
		GetIdx(b,e,-1,dst,0,s,1);
	}
	int get(int x){
		return buf[x+s];
	}
};
inline int xorshift(){
	static int w=1145141919;
	w=w^(w<<17);
	w=w^(w>>13);
	w=w^(w<<5);
	return w;
}
struct Node{
	Node *l,*r;
	int v,s;
} buf[200010];
Node* Merge(Node*a,Node*b){
	if(!a)return b;
	if(!b)return a;
	int s=a->s+b->s,x=xorshift()%s;
	if(x<a->s){
		a->r=Merge(a->r,b);
		a->s=s;
		return a;
	}else{
		b->l=Merge(a,b->l);
		b->s=s;
		return b;
	}
}
using pn=pair<Node*,Node*>;
pn Split(Node*x,int t){
	if(!x)return pn(0,0);
	if(t<=x->v){
		pn c=Split(x->l,t);
		if(c.first)x->s-=c.first->s;
		x->l=c.second;
		return pn(c.first,x);
	}else{
		pn c=Split(x->r,t);
		if(c.second)x->s-=c.second->s;
		x->r=c.first;
		return pn(x,c.second);
	}
}
int MaxValue(Node* x){
	while(x->r)x=x->r;
	return x->v;
}
void Show(Node* x){
	if(!x)return;
	Show(x->l);
	cerr<<x->v<<" ";
	Show(x->r);
}
int main(){
	int n=read();
	SegTree seg(n*2);
	vector<Node*> trs(n*2);
	vi mx(n*2,-1);
	REP(i,n){
		int x=read()-1;
		seg.Update(i,x);
		trs[i]=buf+i;
		trs[i]->v=x;
		trs[i]->s=1;
		mx[i]=x;
	}
	vi idx;
	int sum=0;
	FOR(i,n,n*2){
		idx.clear();
		seg.GetIdx(0,i,idx);
		int last=-1;
		Node*x=0;
		sum+=idx.size();
		for(auto j:idx){
			LN;
			pn c=Split(trs[j],last);
			LN;
			last=mx[j];
			LN;
			if(c.first)
				mx[j]=MaxValue(c.first);
			else
				mx[j]=-1;
			LN;
			seg.Update(j,mx[j]);
			LN;
			trs[j]=c.first;
			LN;
			x=Merge(x,c.second);
			LN;
		}
		if(x->s==n){
			cout<<i-n<<endl;
			return 0;
		}
		if(sum>=2e6)return 0;
		mx[i]=last;
		seg.Update(i,mx[i]);
		trs[i]=x;
		//Show(x);
	}
}