这个题一开始感觉是想的差不多了，，然而不知道为什么没继续想（貌似是没考虑到treap的插入改怎么搞之类的）

那么这个题直接蹩脚的用treap模拟一下插入，然后枚举答案，在序列里二分就好了，最后答案就是max(ans[i],ans[i-1])（后面肯定不能比前面小吧）

1 #include 
     
       2 #define LL long long 3 #define inf 0x3f3f3f3f 4 using namespace std; 5 inline int ra() 6 { 7     int x=0,f=1; char ch=getchar(); 8     while (ch<'0' || ch>'9') {
   if (ch=='-') f=-1; ch=getchar();} 9     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}10     return x*f;11 }12 int n,sz,root,now,mx;13 int mn[100005],ans[100005];14 int v[100005],size[100005],rnd[100005],ls[100005],rs[100005];15 void update(int x){size[x]=size[ls[x]]+size[rs[x]]+1;}16 void rturn(int &x){
   int t=ls[x]; ls[x]=rs[t]; rs[t]=x; update(x); update(t); x=t;}17 void lturn(int &x){
   int t=rs[x]; rs[x]=ls[t]; ls[t]=x; update(x); update(t); x=t;}18 void insert(int &k, int x)19 {20     if (!k){21         k=++sz; size[k]=1; rnd[k]=rand();22         return;23     }24     size[k]++;25     if (size[ls[k]]