rt，一直 wa*3

#include<bits/stdc++.h>
#define int long long
#define pii std::pair<int,int>
#define mk(P,Q) std::make_pair((P),(Q))
#define rep(j,k,z) for(int i=j;i<=k;i+=z)
#define per(j,k,z) for(int i=j;i>=z;i-=z)
#define ok std::cout<<"orzsoutherndynasty\n"

const int maxn=2e5+10;

int a[maxn],c[maxn];

int n,q;

struct node{
	int l,r,sum,lz;
}s[maxn<<2];

void build(int l,int r,int p){
	s[p].l=l,s[p].r=r;
	if(l==r){
		s[p].sum=(a[l]!=0);
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	s[p].sum=s[p*2].sum+s[p*2+1].sum;
	return ;
}

void upd(int k,int x,int p){
	int l=s[p].l,r=s[p].r;
	if(l==r&&l==k){
		s[p].sum+=x;
		return ;
	}
	int mid=(l+r)>>1;
	if(k<=mid) upd(k,x,p*2);
	else upd(k,x,p*2+1);
	s[p].sum+=x;
	return ;
}

int query(int p){
	int l=s[p].l,r=s[p].r;
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(s[p*2].sum<mid-l+1) return query(p*2);
	else if(s[p*2+1].sum<r-mid) return query(p*2+1);
	return n;
}

signed main(){
	std::cin>>n>>q;
	rep(1,n,1){
		int opt;
		std::cin>>opt;
		if(opt>=n) opt=n;
		a[opt]++;
		c[i]=opt;
	}
	build(0,n-1,1);
	while(q--){
		int x,y;
		std::cin>>x>>y;
//		if(y>=n) y=n;
		if(c[x]<n) a[c[x]]--;
		if(y<n) a[y]++;
		if(c[x]<n&&a[c[x]]==0) upd(c[x],-1,1);
		c[x]=y;
		if(y<n&&a[y]==1) upd(y,1,1);
		std::cout<<query(1)<<'\n';
	}
	return 0;
}