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)

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 114514;
}

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