Submission #1268684

---

Source Code Expand

#include<iostream>
using namespace std;
int n,p[1<<18],q[1<<18],t[1<<18],f[1<<18];
bool circle(int a,int b,int c){return q[a]<q[b]&&q[b]<q[c]||q[b]<q[c]&&q[c]<q[a]||q[c]<q[a]&&q[a]<q[b];}
main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>p[i];
		q[p[i]]=i;
	}
	f[n]=n;
	for(int i=n;--i;)
	{
		if(t[i+1])
		{
			if(circle(f[i+1],i,i+1))
			{
				t[i]=t[i+1],f[i]=f[i+1];
			}
			else
			{
				t[i]=t[i+1]+1,f[i]=i+1;
			}
		}
		else
		{
			if(q[i]<q[i+1])
			{
				t[i]=0,f[i]=i;
			}
			else
			{
				t[i]=1,f[i]=i+1;
			}
		}
	}
	cout<<t[1]<<endl;
}

Submission Info

Judge Result