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;

mt19937 rnd(time(0));
const int maxn=200005;
int n;
int a[maxn*2],rt[maxn*2];
vector<int>idx;

namespace Treap{
	int tot;
	class Node{
	public:
		int l,r,fix,sz,v,vr;
	}t[maxn];
	int newnode(int _v){
		tot++;
		t[tot].l=t[tot].r=0;
		t[tot].fix=rnd();
		t[tot].v=t[tot].vr=_v;
		t[tot].sz=1;
		return tot;
	}
	void pushup(int cur){
		t[cur].vr=t[cur].v;
		if(t[cur].r)t[cur].vr=t[t[cur].r].vr;
		t[cur].sz=t[t[cur].l].sz+t[t[cur].r].sz+1;
	}
	void split(int cur,int &x,int &y,int val){
		if(!cur)x=y=0;
		else if(t[cur].v<=val){
			x=cur;
			split(t[cur].r,t[x].r,y,val);
			pushup(x);
		}
		else{
			y=cur;
			split(t[cur].l,x,t[y].l,val);
			pushup(y);
		}
	}
	void merge(int &cur,int x,int y){
		if(!x||!y)cur=x?x:y;
		else if(t[x].fix<t[y].fix){
			cur=x;
			merge(t[cur].r,t[x].r,y);
			pushup(cur);
		}
		else{
			cur=y;
			merge(t[cur].l,x,t[y].l);
			pushup(cur);
		}
	}
	void print(int cur){
		if(!cur)return;
		print(t[cur].l);
		printf("%d ",t[cur].v);
		print(t[cur].r);
	}
}

namespace Segtree{
	int mx[maxn*8];
	void update(int cur,int l,int r,int k){
		if(l==r){
			mx[cur]=a[l];
			return;
		}
		int mid=l+r>>1;
		if(k<=mid)update(cur<<1,l,mid,k);
		else update(cur<<1|1,mid+1,r,k);
		mx[cur]=max(mx[cur<<1],mx[cur<<1|1]);
	}
	void query(int cur,int l,int r,int &x,vector<int>&pos){
		if(mx[cur]<=x)return;
		if(l==r){
			pos.push_back(l);
			x=mx[cur];
			return;
		}
		int mid=l+r>>1;
		query(cur<<1,l,mid,x,pos);
		query(cur<<1|1,mid+1,r,x,pos);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		rt[i]=Treap::newnode(a[i]);
		Segtree::update(1,1,2*n,i);
	}
	for(int i=n+1;i<=2*n;i++){
		idx.clear();
		int last=0;
		Segtree::query(1,1,2*n,last,idx);
		for(int j=0;j<int(idx.size());j++){
			int p=idx[j];
			int x,y;
			Treap::split(rt[p],x,y,Treap::t[rt[i]].vr);
			rt[p]=x;
			a[p]=Treap::t[x].vr;
			Segtree::update(1,1,2*n,p);
			Treap::merge(rt[i],rt[i],y);
		}
		if(Treap::t[rt[i]].sz==n){
			printf("%d\n",i-n-1);
			return 0;
		}
		a[i]=Treap::t[rt[i]].vr;
		Segtree::update(1,1,2*n,i);
	}
	return 0;
}