题解，但不是回文数

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 100007
using namespace std;
struct Splay{
	int val,fa,s[2],size;
}t[N];
struct Node{
	int num,val;
}a[N];
int c[N];
int root,T,n=0,cnt=0,m,num=0,f[N];
bool Cmp(const Node a,const Node b){
    return a.val<b.val;
}
void update(int p){
    t[p].size=t[t[p].s[0]].size+t[t[p].s[1]].size+1;
}
int wich(int x){
    return t[t[x].fa].s[0]==x? 0:1;
}
void connect(int x,int y,int f){
    t[x].fa=y;t[y].s[f]=x;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,int val){
    while(x<=n){
        c[x]=max(c[x],val);
        x+=lowbit(x);
    }
}
int query(int x){
    int ret=0;
    while(x){
        ret=max(ret,c[x]);x-=lowbit(x);
    }
    return ret;
}
void rotate(int x){
	int y=t[x].fa,rt=t[y].fa;
	int ys=wich(x),rts=wich(y);
	connect(t[x].s[ys^1],y,ys);
	connect(y,x,ys^1);connect(x,rt,rts);
	update(y);update(x);
}

void rota(int p){
	if(wich(p)==wich(t[p].fa)){rotate(t[p].fa);rotate(p);}
	else{rotate(p);rotate(p);}
}

void splay(int p,int to)
{
	if(!p) return;
	if(p==to) return;
	if(to==root) root=p;
	while(1)
	{
		if(t[p].fa==to){rotate(p);return;}
		if(t[t[p].fa].fa==to){rota(p);return;}
		rota(p);
	}
}

int find(int x)
{
	int p=root;
	while(p)
	{
		if(x<=t[t[p].s[0]].size) p=t[p].s[0];
		else if(x==t[t[p].s[0]].size+1) return p;
		else{x-=t[t[p].s[0]].size+1;p=t[p].s[1];}
	}
	return 0;
}
void insert(int val,int k)
{
	int l=find(k+1),r=find(k+2);
	splay(l,root);
	splay(r,t[root].s[1]);
	t[++cnt]=(Splay){val,t[root].s[1],{0,0},1};
	t[t[root].s[1]].s[0]=cnt;
	update(t[root].s[1]);update(root);
	splay(cnt,root);
}

void dfs(int p)
{
	if(t[p].s[0]) dfs(t[p].s[0]);
	if(t[p].val!=INF&&t[p].val!=-INF)
		a[++num].val=t[p].val;
	if(t[p].s[1]) dfs(t[p].s[1]);
}
int main()
{
	t[++cnt]=(Splay){-INF,0,{0,2},2};
	t[++cnt]=(Splay){INF,1,{0,0},1};
	scanf("%d",&n); 
	int x;
	root=1;
	for(int i=1; i<=n; i++)
		scanf("%d",&x),insert(i,x);
	dfs(root);
	for(int i=1; i<=n; i++) a[i].num=i;
	sort(a+1,a+1+n,Cmp);
	int ans=0;
	for(int i=1; i<=n; i++)
	{
		int maxx=query(a[i].num);
		add(a[i].num,++maxx);
		ans=max(ans,maxx);
		printf("%d\n",ans);
	}
}