Description
天才麻将少女KPM立志要在日麻界闯出一番名堂。
KPM上周叒打了n场麻将，但她这次又没控分，而且因为是全市参与的麻将大赛，所以她的名次范围是0..10^5。
名次可能等于0是因为KPM那场没去打= =
没去打就意味着无限的可能性。
KPM叒想要让自己的名次严格递增。为了避免被妹子怀疑，她只能把没打的比赛的名次改成T..R中的整数
当然，n场全部严格递增是很难做到的。你只需要求出可能的最长递增子序列长度就好了。
Input
第一行三个整数n,T,R。
第二行n个整数，表示n场的排名。
Output
可能的最长递增子序列长度。
Sample Input
5 1 4
3 0 5 9 2
Sample Output
4
HINT
对于100%的数据:
自己的代码没有写差分，又丑又慢QAQ
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define LL long long
using namespace std;
const int N=2e5+;
int n,L,R,a,tmp,cnt=1e5;
int root,rt1,rt2,rt3,st[N],ch[N][];
#define lc ch][0
#define rc ch][1
#define rnd ch][2
#define sz ch][3
#define v ch][4
#define tag ch][5
#define mx ch][6
#define mn ch][7
#define cov ch][8
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void up(int w)
{
w[sz]=w[lc][sz]+w[rc][sz]+;w[mx]=w[mn]=w[v];
if(w[lc])w[mx]=max(w[mx],w[lc][mx]),w[mn]=min(w[mn],w[lc][mn]);
if(w[rc])w[mx]=max(w[mx],w[rc][mx]),w[mn]=min(w[mn],w[rc][mn]);
}
void dn(int w)
{
if(w[cov])
{
w[lc][v]=w[lc][cov]=w[lc][mx]=w[lc][mn]=w[cov];
w[rc][v]=w[rc][cov]=w[rc][mx]=w[rc][mn]=w[cov];
w[lc][tag]=w[rc][tag]=;
w[cov]=;
}
if(w[tag])
{
w[lc][v]+=w[tag];w[lc][tag]+=w[tag];
w[lc][mx]+=w[tag];w[lc][mn]+=w[tag];
w[rc][v]+=w[tag];w[rc][tag]+=w[tag];
w[rc][mx]+=w[tag];w[rc][mn]+=w[tag];
w[tag]=;
}
}
void dfs(int w){if(!w)return;dfs(w[lc]);dfs(w[rc]);up(w);}
int build()
{
int top=;
for(int w=;w<=1e5;w++)
{
w[rnd]=rand();
while(top&&st[top][rnd]>w[rnd])
{
st[top][rc]=w[lc];
w[lc]=st[top--];
}
st[top][rc]=w;st[++top]=w;
}
ch[][]=;dfs(st[]);
return st[];
}
void split(int w,int& l,int& r,int k)
{
if(!w){l=r=;return;}
dn(w);int lson=w[lc][sz];
if(k<=lson){r=w;split(w[lc],l,w[lc],k);}
else{l=w;split(w[rc],w[rc],r,k-lson-);}
up(w);
}
int merge(int a,int b)
{
if(!a||!b)return a+b;
if(a[rnd]<b[rnd]){dn(a);a[rc]=merge(a[rc],b);up(a);return a;}
else{dn(b);b[lc]=merge(a,b[lc]);up(b);return b;}
}
int rank(int w,int k)
{
if(!w)return ;dn(w);
int lson=w[lc][sz];
if(k==lson+)return w[v];
if(k<=lson)return rank(w[lc],k);
else return rank(w[rc],k-lson-);
}
void ins(int& w,int x,int k)
{
dn(w);
if(x[rnd]<w[rnd]||!w){split(w,x[lc],x[rc],k);w=x;up(w);return;}
int lson=w[lc][sz];
if(k<=lson)ins(w[lc],x,k);
else ins(w[rc],x,k-lson-);
up(w);
}
void del(int& w,int k)
{
dn(w);
int lson=w[lc][sz];
if(k==lson+){w=merge(w[lc],w[rc]);return;}
if(k<=lson)del(w[lc],k);
else del(w[rc],k-lson-);
up(w);
}
void add(int L,int R,int V)
{
rt1=rt2=rt3=;split(root,rt2,rt3,R);
root=rt2;rt2=;split(root,rt1,rt2,L-);
rt2[tag]+=V;rt2[v]+=V;rt2[mx]+=V;rt2[mn]+=V;
root=merge(rt1,rt2);root=merge(root,rt3);
}
void cover(int w,int V)
{
if(!w||w[mn]>=V)return;
dn(w);if(w[v]<V)w[v]=V;
if(w[mx]<=V){w[cov]=V;w[tag]=;up(w);return;}
cover(w[lc],V);cover(w[rc],V);
up(w);
}
void update(int L,int R,int V)
{
rt1=rt2=rt3=;split(root,rt2,rt3,R);
root=rt2;rt2=;split(root,rt1,rt2,L-);
cover(rt2,V);
root=merge(rt1,rt2);root=merge(root,rt3);
}
int main()
{
n=read();L=read();R=read();root=build();
for(int i=;i<=n;i++)
{
a=read();
if(a>)
{
tmp=rank(root,a-)+;
update(a,1e5,tmp);
}
else
{
del(root,R);cnt++;
tmp=rank(root,L-);
cnt[v]=tmp;cnt[rnd]=rand();
ins(root,cnt,L-);
add(L,R,);tmp=rank(root,R);
if(R!=1e5)update(R+,1e5,tmp);
}
}
printf("%d",root[mx]);
return ;
}