rt,WA on #1#2

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int read();
struct Node{
	int v,left,right;
}t[N*4];
void pushup(int k)
{
	t[k].v=max(t[k<<1].v,t[k<<1|1].v);
}
void build(int k,int l,int r)
{
	t[k].left=l; t[k].right=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(k<<1,l,mid); build(k<<1|1,mid+1,r);
	pushup(k);
}
void update(int k,int p,int v)
{
	if(t[k].left==p && t[k].right==p)
	{
		t[k].v=max(t[k].v,v);
		return;
	}
	int mid=t[k].left+t[k].right>>1;
	if(p<=mid) update(k<<1,p,v);
	else update(k<<1|1,p,v);
	pushup(k);
}
int query(int k,int l,int r)
{
	if(t[k].left>=l && t[k].right<=r) return t[k].v;
	int mid=t[k].left+t[k].right>>1,ret=0;
	if(l<=mid) ret=max(ret,query(k<<1,l,r));
	if(r>mid) ret=max(ret,query(k<<1|1,l,r));
	return ret;
}
int n,ans;
int a[N],vis[N],dp[N][2];
int main()
{
	n=read(); build(1,1,N);
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) dp[i][1]=1;
	for(int i=1;i<=n;i++)
	{
		if(vis[a[i]]) dp[i][0]=dp[vis[a[i]]][1]+1;
		if(1<=a[i]-1) dp[i][1]=max(dp[i][1],query(1,1,a[i]-1)+1);
		if(a[i]+1<=n) dp[i][1]=max(dp[i][1],query(1,a[i]+1,n)+1);
		update(1,a[i],dp[i][0]); vis[a[i]]=i; ans=max(ans,dp[i][0]);
	}
	printf("%d",ans);
	return 0;
}
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<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}