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 mod 998244353
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int maxn=2e5+10;
int n,root;
int p[maxn],key[maxn];
int ch[maxn][2],val[maxn],mx[maxn],mn[maxn],good[maxn];
inline void upd(int x)
{
	mn[x]=val[x];
	mx[x]=val[x];
	good[x]=1;
	if(ch[x][0])
	{
		if((!good[ch[x][0]])||mx[ch[x][0]]>val[x])good[x]=0;
		if(good[x])
		{
			mn[x]=mn[ch[x][0]];
		}
		else
		{
			mn[x]=mn[ch[x][0]]<mn[x]?mn[ch[x][0]]:mn[x];
			mx[x]=mx[ch[x][0]]>mx[x]?mx[ch[x][0]]:mx[x];
		}
	}
	if(ch[x][1])
	{
		if(good[x]&&((!good[ch[x][1]])||val[x]>mn[ch[x][1]]))good[x]=0;
		if(good[x])
		{
			mx[x]=mx[ch[x][1]];
		}
		else
		{
			mn[x]=mn[ch[x][1]]<mn[x]?mn[ch[x][1]]:mn[x];
			mx[x]=mx[ch[x][1]]>mx[x]?mx[ch[x][1]]:mx[x];
		}
	}
}
inline int merge(int p,int q)
{
//	cout<<"merge "<<p<<" "<<q<<endl;
	if(!p||!q)return p+q;
	if(key[p]>key[q])
	{
		ch[p][1]=ch[p][1]?merge(ch[p][1],q):q;
		upd(p);
		return p;
	}
	else
	{
		ch[q][0]=ch[q][0]?merge(p,ch[q][0]):p;
		upd(q);
		return q;
	}
}
inline void upd2(int x)
{
	mn[x]=ch[x][0]?mn[ch[x][0]]:val[x];
	mx[x]=ch[x][1]?mx[ch[x][1]]:val[x];
	good[x]=1;
}
inline int merge2(int p,int q)
{
//	cout<<"merge "<<p<<" "<<q<<endl;
	if(!p||!q)return p+q;
	if(key[p]>key[q])
	{
		ch[p][1]=ch[p][1]?merge2(ch[p][1],q):q;
		upd2(p);
		return p;
	}
	else
	{
		ch[q][0]=ch[q][0]?merge2(p,ch[q][0]):p;
		upd2(q);
		return q;
	}
}
inline pii solve(int x,int bound)
{
	if(!x)return make_pair(0,0);
//	cout<<"solve "<<val[x]<<" "<<bound<<" "<<mx[x]<<" "<<good[x]<<endl;//system("pause");
	if(mx[x]<bound)return make_pair(0,x);
	pii res;
	if(good[x])
	{
		if(mn[x]>bound)return make_pair(x,0);
		
		if(!ch[x][0]||(bound>val[x]))
		{
			res=solve(ch[x][1],bound);
			ch[x][1]=0;
			if(ch[x][0])upd2(x);
			else
			{
				mn[x]=mx[x]=val[x];
				good[x]=1;
			}
			res.second=merge(x,res.second);
			return res;
		}
		else
		{
			res=solve(ch[x][0],bound);
			ch[x][0]=0;
			upd2(x);
			res.first=merge2(res.first,x);
			return res;
		}
	}
	pii lft=solve(ch[x][0],bound);
	if(lft.first)bound=mx[lft.first];
	int rson=ch[x][1];
	ch[x][0]=ch[x][1]=0;
	upd(x);
	if(val[x]>bound)
	{
		lft.first=merge2(lft.first,x);
		bound=val[x];
	}
	else
	{
		lft.second=merge(lft.second,x);
	}
	pii rht=solve(rson,bound);
	return make_pair(merge2(lft.first,rht.first),merge(lft.second,rht.second));
}
vector<int> a;
int main()
{
	scanf("%d",&n);
/*	n=200000;
	a.resize(n);
	for(int i=0;i<n;i++)a[i]=i+1;
	random_shuffle(a.begin(),a.end());
	for(int i=1;i<=n;i++)p[i]=a[i-1];*/
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
	{
		val[i]=p[i];
	//	cout<<p[i]<<endl;
		mx[i]=mn[i]=p[i];
		good[i]=1;
		key[i]=rand();
		root=merge(root,i);
	//	cout<<root<<endl;
	}
//	cout<<"here\n";
//	cout<<val[root]<<endl;
	int turn=0;
	pii res;
	while(!good[root])
	{
		turn++;
	//	if(turn%10000==0)cout<<turn<<endl;
		res=solve(root,0);
	//	system("pause");
		root=merge(res.second,res.first);
	}
	printf("%d\n",turn);
	return 0;
}