先考虑对于一个序列，能使其可以删空的的修改次数。
首先可以发现，序列的排列顺序是没有影响的，所以可以将所有数放到桶里来处理。
尝试对一个没有经过修改的可以删空的序列来进行删数，一开始删去所有的\(n\)，然后序列长度变为\(x_1\)，删去所有的\(x_1\)，然后序列长度变为\(x_2\)，删去所有的\(x_2\)……直到对于一个长度为\(x_i\)的序列，其中没有\(x_i\)这个数，那么此时就要对序列执行修改操作了。
考虑过程，当不能连续的删数时，就需要通过修改来填补空缺。实际上，对\([1,n]\)做前缀和，存在数字的位置需满足该位置的值等于该位置的下标，不然就需进行修改。
可以发现对于\([1,n]\)的每个出现的数字，从其往前覆盖一条长度为该数出现次数的线段，区间\([1,n]\)未被覆盖的位置个数即为需要修改的次数。
可以通过线段树来维护最小值的个数来统计未被覆盖的位置个数。
考虑加上修改操作，单点修改直接改修改前后两个数的贡献即可，整体加减可以对线段树的询问加上偏移量，比如当整体加一时，偏移量减一，询问的区间向左移动。
然后对于一些不在当前询问区间的数字的贡献需要忽略，我的处理是在询问区间右边的数字就不再计算贡献。
\(code:\)
#include<bits/stdc++.h>
#define maxn 2000010
#define all 450000
#define ls (cur<<1)
#define rs (cur<<1|1)
#define mid ((l+r)>>1)
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,root=1,delta=150000;
int a[maxn],cnt[maxn],add[maxn];
struct node
{
int mi,cnt;
}t[maxn];
node operator +(const node &a,const node &b)
{
if(a.mi<b.mi) return a;
if(a.mi>b.mi) return b;
return (node){a.mi,a.cnt+b.cnt};
}
void pushadd(int cur,int v)
{
t[cur].mi+=v,add[cur]+=v;
}
void pushdown(int cur)
{
if(!add[cur]) return;
pushadd(ls,add[cur]),pushadd(rs,add[cur]),add[cur]=0;
}
void build(int l,int r,int cur)
{
if(l==r)
{
t[cur]=(node){0,1};
return;
}
build(l,mid,ls),build(mid+1,r,rs),t[cur]=t[ls]+t[rs];
}
void modify(int L,int R,int l,int r,int v,int cur)
{
if(L>R) return;
if(L<=l&&R>=r)
{
pushadd(cur,v);
return;
}
pushdown(cur);
if(L<=mid) modify(L,R,l,mid,v,ls);
if(R>mid) modify(L,R,mid+1,r,v,rs);
t[cur]=t[ls]+t[rs];
}
node query(int L,int R,int l,int r,int cur)
{
if(L<=l&&R>=r) return t[cur];
pushdown(cur);
if(R<=mid) return query(L,R,l,mid,ls);
if(L>mid) return query(L,R,mid+1,r,rs);
return query(L,R,l,mid,ls)+query(L,R,mid+1,r,rs);
}
int main()
{
read(n),read(m),build(1,all,root);
for(int i=1;i<=n;++i)
read(a[i]),a[i]+=delta,cnt[a[i]]++;
for(int i=1+delta;i<=n+delta;++i)
modify(i-cnt[i]+1,i,1,all,1,root);
while(m--)
{
int p,x;
read(p),read(x);
if(p)
{
if(a[p]<=n+delta) modify(a[p]-cnt[a[p]]+1,a[p]-cnt[a[p]]+1,1,all,-1,root);
cnt[a[p]]--,x+=delta,cnt[x]++,a[p]=x;
if(x<=n+delta) modify(x-cnt[x]+1,x-cnt[x]+1,1,all,1,root);
}
else
{
if(x==1) p=n+delta,modify(p-cnt[p]+1,p,1,all,-1,root),delta--;
else delta++,p=n+delta,modify(p-cnt[p]+1,p,1,all,1,root);
}
node q=query(1+delta,n+delta,1,all,root);
if(q.mi) puts("0");
else printf("%d\n",q.cnt);
}
return 0;
}