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 <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<ctime>
#include<set>
#include<queue>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);++(i))
#define fd1(i,n) for ((i)=(n);(i)>=1;--(i))
#define fz0g(i,n) for ((i)=0;(i)<=(n);++(i))
#define fd0g(i,n) for ((i)=(n);(i)>=0;--(i))
#define fz0k(i,n) for ((i)=0;(i)<(n);++(i))
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;--(i))
#define fz(i,x,y) for ((i)=(x);(i)<=(y);++(i))
#define fd(i,y,x) for ((i)=(y);(i)>=(x);--(i))
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
using namespace std;
int n,m,i,j,lc[200005],rc[200005],a[200005],sz[200005],rnd[200005],rt[400005],dep[200005],lst[400005];
struct bit
{
	int a[200005];
	void add(int x,int y)
	{
		int i;
		for(i=x;i;i-=(i&-i)) a[i]=max(a[i],y);
	}
	int query(int x)
	{
		int i,s=0;
		for(i=x;i<=n;i+=(i&-i)) s=max(s,a[i]);
		return s;
	}
}tr;
void pushup(int x)
{
	sz[x]=sz[x+x]+sz[x+x+1]+1;
}
int rst(int x)
{
	while(rc[x]) x=rc[x];
	return a[x];
}
void split(int x,int y,int &l,int &r)
{
	if(!x){
		l=r=0;
		return;
	}
	if(y<=a[x]){
		split(lc[x],y,l,lc[x]);r=x;
		pushup(r); 
	}
	else{
		split(rc[x],y,rc[x],r);l=x;
		pushup(l);
	}
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(rnd[x]>rnd[y]){
		rc[x]=merge(rc[x],y);
		pushup(x);
		return x;
	}
	else{
		lc[y]=merge(x,lc[y]);
		pushup(y);
		return y;
	}
}
int main()
{
	scanf("%d",&n);
	fz1(i,n){
		scanf("%d",&a[i]);
		dep[i]=tr.query(a[i])+1;m=max(m,dep[i]);
		tr.add(a[i],dep[i]);
		sz[i]=1;rnd[i]=rand()*32768+rand();
		rt[dep[i]]=merge(rt[dep[i]],i);
	}
	fz1(i,m){
		lst[i]=rst(rt[i]);
	}
	fz1(i,m-1){
		while(rt[i]){
			int t=rst(rt[i]),l=i+1,r=m+1,mid,ans=i;
			while(l<r){
				mid=(l+r)/2;
				if(lst[mid]>t){
					l=mid+1;
					ans=mid;
				}
				else r=mid;
			}
			if(ans==m){
				m++;
			}
			int t1,t2;
			split(rt[i],lst[ans+1],t1,t2);
			rt[i]=t1;rt[ans+1]=merge(rt[ans+1],t2);
			lst[i]=rst(rt[i]);lst[ans+1]=rst(rt[ans+1]);
		}
	}
	printf("%d\n",m-1);
	return 0;
}