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 debug pt(rt),cerr<<'\n'
const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}

const int N=2e5+50;
int n,a[N],nowmx;
inline unsigned int unit() {static unsigned int x=19260817; x^=(x<<13); x^=(x>>17); x^=(x<<5); return x;}
inline int Max(int x,int y) {return (x>y) ? x : y;}
struct node {
	node *lc,*rc;
	unsigned int pri;
	int val,sze,mx,all,tag; 
	node() : lc(NULL),rc(NULL),pri(unit()),sze(0),mx(0),all(1) {}
	inline void upt() {
		mx=Max(Max(rc->mx,lc->mx),val);
		sze=lc->sze+rc->sze+1;
		all=lc->all&rc->all&tag;
	}
} *rt,*nowrt,Pool[N],*pool=Pool,*null=pool;
typedef pair <node*,node*> pii;
inline node* merge(node *x,node *y) {
	if(y==null) return x;
	if(x==null) return y;
	if(x->pri>y->pri) {
		x->rc=merge(x->rc,y);
		x->upt(); return x;
	} else {
		y->lc=merge(x,y->lc);
		y->upt(); return y;
	}
}
inline pii split(node *x,int sze) {
	if(x==null) return pii(null,null);
	if(x->lc->sze>=sze) {
		pii tr=split(x->lc,sze);
		x->lc=tr.second; x->upt();
		return pii(tr.first,x);
	} else {
		pii tr=split(x->rc,sze-x->lc->sze-1);
		x->rc=tr.first; x->upt();
		return pii(x,tr.second);
	}
}
inline void Merge(node *&x,node *y) {
	if(y==null) {return;}
	if(x==null) {x=y; return;}
	node *t=x; while(t->rc!=null) t=t->rc;
	node *t2=y; static node* stk[N]; int top=0;
	while(t2->lc!=null) stk[++top]=t2, t2=t2->lc;
	t2->tag=(t2->val>t->val) ? 1 : 0; t2->upt();
	while(top) stk[top--]->upt();
	x=merge(x,y);
}
inline pii split_val(node *x,int lim) {
	if(x==null) return pii(null,null);
	if(Max(x->val,x->lc->mx)<lim) {
		pii tr=split_val(x->rc,lim);
		x->rc=tr.first; x->upt();
		return pii(x,tr.second); 
	} else {
		pii tr=split_val(x->lc,lim);
		x->lc=tr.second; x->upt();
		return pii(tr.first,x);
	}
}
inline pii split_all(node *x) {
	if(x==null) return pii(null,null);
	if(!(x->lc->all&x->tag)) {
		pii tr=split_all(x->lc);
		x->lc=tr.second; x->upt();
		return pii(tr.first,x); 
	} else {
		pii tr=split_all(x->rc);
		x->rc=tr.first; x->upt();
		return pii(x,tr.second);
	}
}
inline node* find_nxt(int lim) {
	pii tr=split_val(rt,lim);
	pii tr2=split_all(tr.second);
	Merge(nowrt,tr.first);
	rt=tr2.second; 
	return tr2.first;
}
inline node* newnode() {
	node *t=++pool;
	t->lc=t->rc=null;
	return t;
}
node* q[N]; int qt;
int main() {
	n=rd(); rt=null; nowmx=n;
	for(int i=1;i<=n;i++) a[i]=rd();
	for(int i=0;i<=n;i++) {
		node *t=newnode();
		t->val=a[i]; t->sze=1; t->mx=a[i];
		t->all=(i ? (a[i]>a[i-1]) : 1);
		t->tag=t->all; 
		rt=merge(rt,t);
	}
	int step=0;
	while(!rt->all) {
		++step;
		int mxval=1, pos=0;
		qt=0;
		nowrt=null;
		while(mxval<nowmx) 
			mxval=(q[++qt]=find_nxt(mxval))->mx;
		Merge(nowrt,rt); rt=nowrt;
		for(int i=1;i<=qt;i++) Merge(rt,q[i]);
		while(nowmx>3) {
			pii tr=split(rt,nowmx);
			if(tr.second->val==nowmx) rt=tr.first, --nowmx;
			else {rt=merge(tr.first,tr.second); break;}
		}
	}
	cout<<step<<'\n';
}