WA 1,3,5,6,8

#include<bits/stdc++.h>
#define test cout<<a[i].k<<endl
using namespace std;
struct nood {
	int v,k;
}a[200001];
bool cmp(nood a,nood b){
	return a.v<b.v;
}
int s=1,n;
bool pd=false;
int main(){
//	freopen("in.txt","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].v;
		a[i].k=i;
	}
	sort(a+1,a+n+1,cmp);
	a[0].k=0x4f4f4f;
	int maxn,minn,j;
	for(int i=1;i<=n;i++){
		maxn=a[i].k,minn=a[i].k;
		for(j=i;j<=n;j++) {
			maxn=max(a[j].k,maxn),minn=min(a[j].k,minn);
			if(a[i].v!=a[j].v) break;
		}
		j--;
		if(j!=i){
			if(pd){
				if(minn>=a[i-1].k) {
					a[j].k=maxn;
					i=j; 
				}
				else {
					s++;
					a[j].k=minn;
					i=j;
					pd=false;
				}
			}
			else{
				if(maxn<=a[i-1].k) {
					a[j].k=minn;
					i=j; 
				}
				else {
					pd=true;
					a[j].k=maxn;
					i=j;
				}
			}
		}
	/*	else{
			if((a[i-1].k<a[i].k)!=pd){
				if(pd==false) {
					pd=true;
				}
				else {
					s++;
					pd=false;
				}
			}
		}*/
	}
	cout<<s<<endl;
	return 0;
}