#include<bits/stdc++.h>
#define ll long long
#define N 200001
using namespace std;
ll n,q,x,y,ans,a[N],cnt[N],maxx,id,fz;
int main(){
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    while(q--){
        cin>>x>>y;
        cnt[a[x]]--;
        cnt[y]++;
        a[x]=y;
        for(int i=1;i<=n;i++) maxx=max(maxx,cnt[i]);
        for(int i=1;i<n;i++){
            if(cnt[i]==0) continue;
            fz=max(maxx-cnt[i],(ll)1);
            for(int j=n;j>i;j--)
            if(cnt[j]>=fz){
                id=j;
                break;
            }
            ans=max(ans,id-i);
            id=0;
        }
        cout<<ans<<endl;
        ans=0;
    }
    return 0;
}