#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid(l,r) (l+r>>1)
#define lowbit(x) (x&-x)
#define sqrt sqrtl
using namespace std;
const int N=5e5+10,M=1+10,mod=1e9+7;
const double eps=1e-1;
const long double pi=acos(-1);
int n,m,a[N],p,x,idx=150001,cnt[N];
struct tree{
  int minn,mcnt,cnt,lazy;
}tr[4*N];
void pushup(int u){
  tr[u].minn=min(tr[ls(u)].minn,tr[rs(u)].minn);
  if(tr[ls(u)].minn==tr[u].minn)tr[u].mcnt+=tr[ls(u)].mcnt;
  if(tr[rs(u)].minn==tr[u].minn)tr[u].mcnt+=tr[rs(u)].mcnt;
  tr[u].cnt=tr[ls(u)].cnt+tr[rs(u)].cnt;
}
void build(int l,int r,int u){
  tr[u].mcnt=0;
  if(l==r){
    tr[u].mcnt=tr[u].cnt=1;
    return;
  }
  build(l,mid(l,r),ls(u));
  build(mid(l,r)+1,r,rs(u));
  pushup(u);
}
void pushdown(int l,int r,int u){
  if(tr[u].lazy){
    tr[ls(u)].minn+=tr[u].lazy;
    tr[rs(u)].minn+=tr[u].lazy;
    if(!tr[ls(u)].minn)tr[ls(u)].cnt=tr[ls(u)].mcnt;
    else tr[ls(u)].cnt=0;
    if(!tr[rs(u)].minn)tr[rs(u)].cnt=tr[rs(u)].mcnt;
    else tr[rs(u)].cnt=0;
    tr[ls(u)].lazy+=tr[u].lazy;
    tr[rs(u)].lazy+=tr[u].lazy;
    tr[u].lazy=0;
  }
}
void update(int l,int r,int L,int R,int u,int k){
  if(l>=L&&r<=R){
    tr[u].minn+=k;
    if(!tr[u].minn)tr[u].cnt=tr[u].mcnt;
    else tr[u].cnt=0;
    tr[u].lazy+=k;
    return;
  }
  pushdown(l,r,u);
  if(L<=mid(l,r))update(l,mid(l,r),L,R,ls(u),k);
  if(R>mid(l,r))update(mid(l,r)+1,r,L,R,rs(u),k);
  pushup(u);
}
int query(int l,int r,int L,int R,int u){
  if(l>=L&&r<=R)return tr[u].cnt;
  int ret=0;
  pushdown(l,r,u);
  if(L<=mid(l,r))ret+=query(l,mid(l,r),L,R,ls(u));
  if(R>mid(l,r))ret+=query(mid(l,r)+1,r,L,R,rs(u));
  return ret;
}
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m;
  build(1,450005,1);
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++){
    a[i]+=idx;
    int id=a[i]-cnt[a[i]];
    update(1,450005,id,id,1,1);
    cnt[a[i]]++;
  }
  while(m--){
    cin>>p>>x;
    if(p){
      if(a[p]<=idx+n){
        int id=a[p]-cnt[a[p]]+1;
        update(1,450005,id,id,1,-1);
        cnt[a[p]]--;
      }
      else cnt[a[p]]--;
      a[p]=idx+x;
      if(a[p]<=idx+n){
        int id=a[p]-cnt[a[p]];
        update(1,450005,id,id,1,1);
        cnt[a[p]]++;
      }
      else cnt[a[p]]++;
    }
    else if(x==1){
      int id=idx+n;
      if(cnt[id])update(1,450005,id-cnt[id]+1,id,1,-1);
      idx--;
    }
    else{
      idx++;
      int id=idx+n;
      if(cnt[id])update(1,450005,id-cnt[id]+1,id,1,1);
    }
    cout<<query(1,450005,idx+1,idx+n,1)<<endl;
  }
  return 0;
}

思路参考第一篇题解，求求啦