#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],num[N];
int main(){
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
	    cin>>a[i];
	    ++num[a[i]];
	}
	int x,y,mx,ans,p,idx;
	for(int i=1;i<=m;++i){
	    cin>>x>>y;
	    --num[a[x]];
	    ++num[y];
	    a[x]=y;
	    mx=-1;
	    for(int j=1;j<=n;++j){
	        if(num[j]>=mx){
	            mx=num[j];
            }
        }
        ans=0;
        for(int j=1;j<n-ans;++j){
            if(num[j]==0) continue;
            p=max(mx-num[j],1),idx=0;
            for(int k=n;k>j;--k){
                if(num[k]>=p){
                    idx=k;
                    break;
                } 
            }
            ans=max(idx-j,ans);
        }
        cout<<ans<<"\n";
    }
	return 0;
}