#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,q;
int a[N];
int t[N];
bool check(int x){
	for(int i=1;i<=n-x;i++){
		if(t[i]==0||t[i+x]==0) continue;
		int mx=0;
		for(int j=1;j<=n;j++){
			if(j!=i&&j!=i+x){
				mx=max(mx,t[j]-t[i]);
			}
		}
		if(mx<=t[i+x]) return 1;
	}
	return 0;
}
bool check2(int x){
	int f=1;
	for(int i=1;i<=n-x;i++){
		if(t[i]==0||t[i+x]==0) continue;
		f=0;
		int mx=0;
		for(int j=1;j<=n;j++){
			if(j!=i&&j!=i+x){
				mx=max(mx,t[j]-t[i]);
			}
		}
		if(mx<=t[i+x]) return 1;
	}
	return 0||f;
}
int main(){
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	t[a[i]]++;
	}
	if(n<=100&&q<=100){
		for(int i=1;i<=q;i++){
			int x,y;
			cin>>x>>y;
			t[a[x]]--;
			t[y]++;
			a[x]=y;
			int ans=0;
			for(int j=n-1;j>=0;j--){
				if(check(j)){
					ans=j;
					break;
				}
			}
			cout<<ans<<"\n";
		}	
	}
	else{
		for(int i=1;i<=q;i++){
			int x,y;
			cin>>x>>y;
			t[a[x]]--;
			t[y]++;
			a[x]=y;
			int ans=0;
			int l=0,r=n-1;
			while(l+1<r){
				int mid=(l+r)/2;
				if(check2(mid)){
					if(check(mid)) ans=max(ans,mid);
					if(check(mid+1)) ans=max(ans,mid+1);
					l=mid;
				}
				else{
					r=mid-1;
				}
			}
			if(check(l+1)) ans=max(ans,l+1);
			cout<<ans<<"\n";
		}
	}
    return 0;
} 
/*
8 1 4 2 5 4 2 3
8 1 4 2 5 4 4 3
8 1 4 2 5 4 4 4
8 1 4 1 5 4 4 4
8 1 4 1 8 4 4 4
8 1 4 1 8 4 4 4
*/