Submission #2235674

---

Source Code Expand

#include<iostream>
#include<cstdio>
#define MN 200000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,T,a[MN+5],f[MN+5],pos[MN+5];
bool Check(int a,int b,int c){return (a<b&&b<c)||(a<b&&c<a)||(b<c&&c<a);}
int main()
{
	n=read();
	for(int i=1;i<=n;++i) pos[a[i]=read()]=i;
	for(int i=n;i;--i)
		if(!T&&i!=n&&pos[i]>pos[i+1]) f[T]=i+1,++T; 
		else if(T)
		{
			int F=f[T-1];
			if(!Check(pos[F],pos[i],pos[i+1])) f[T]=i+1,++T;
		}
	cout<<T<<endl;
	return 0;
}

Submission Info

Judge Result