rt，长度 $n \le 10^6$，$O(n \log n)$ 的算法超时了，求助

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[1000001],b[1000001],c,d[1000001],tree[2000001],ans;
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-48;ch=getchar();}
	return x*f;
}
int lowbit(int x)
{
    return x & -x;
}
void xg(int x,int y)
{
    for(int i=x;i<=1000000;i+=lowbit(i))
        tree[i]=max(tree[i],y);
}
int cx(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans=max(ans,tree[i]);
    return ans;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=i;
	for(int i=1;i<=n;i++)
	{
		d[i]=cx(b[a[i]])+1;
		xg(b[a[i]],d[i]);
		ans=max(ans,d[i]);
	}	
	cout<<ans;
	return 0;
}