• $dp[i]$ 表示 $i$ 结尾的最长上升子序列。求出一个最长上升子序列满足不存在 $i\in[i_1,i_2]$，（其中 $i_1,i_2$ 是求出的自序列的相邻两项），使得 $i$ 与 $i_1$ 的 dp 值相同。(意思就是 $i_1$ 不能被 $i$ 代替)

• 则 $i\in[i_1,i_2]$ 只能代替 $i_2$。扫一遍，如果 $i_1<i<i_3$ （$i_3$ 是 $i_2$ 下一个点），则 标记 $i,i_2$ 为 $2$，如果没有 $i$ 满足条件，则标记 $i_2$ 为 $3$ 。 其余未被标记的标记为 $1$。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=x*10+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAX=1e5+5;
int n,a[MAX],C[MAX],f[MAX];

inline void add_max(int x,int v){
	for(;x<=100001;x+=(x&-x))C[x]=max(C[x],v);
} 
inline int pre_max(int x){
	int ret=0;
	for(;x;x-=(x&-x))ret=max(ret,C[x]);
	return ret;
}

int A[MAX],ans[MAX];
signed main(){
//	freopen("in.in","r",stdin);
	n=read();
	for(register int i=1;i<=n;++i)a[i]=read();
	for(register int i=1;i<=n;++i){
		f[i]=max(1,pre_max(a[i]-1)+1);
		add_max(a[i],f[i]);
	}
	int son=0,res=0; 
	for(register int i=1;i<=n;++i){
		if(f[i]>=res){
			res=f[i];
			son=i;
		}
	}
	int k=son,m=1;A[1]=k;
	for(register int j=son;j>=1;--j){
		if(f[j]==f[k]-1){
			A[++m]=j;
			k=j;
		}
	}
	reverse(A+1,A+1+m);
	for(register int i=1;i<=m;++i){
		for(register int j=A[i-1]+1;j<A[i];++j){
			if(a[j]>(i==1?0:a[A[i-1]]) && a[j]< (i==m?1e5+1:a[A[i+1]]))ans[j]=2,ans[A[i]]=2;
		}
		if(!ans[A[i]])ans[A[i]]=3;
	}
	for(register int i=1;i<=n;++i){
		if(!ans[i])ans[i]=1;
		printf("%d",ans[i]);
	}
	
	return 0;
}