#include<bits/stdc++.h>
using namespace std;
int n,q,a[200005],ct[200005],b[200005],c[200005],nn,ps,x,as;
set<int>st[200005],t;
const int I=1e9;
int main(){
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i],ct[a[i]]++;
    for(int i=1;i<=n;i++){
        st[ct[a[i]]].insert(a[i]);
        if(*t.lower_bound(ct[a[i]])!=ct[a[i]]) t.insert(ct[a[i]]);
    }
    while(q--){
        cin>>ps>>x,nn=as=0;
        st[ct[a[ps]]].erase(a[ps]);
        if(st[ct[a[ps]]].empty()) t.erase(ct[a[ps]]);
        ct[a[ps]]--;
        if(ct[a[ps]]&&st[ct[a[ps]]].empty()) if(*t.lower_bound(ct[a[ps]])!=ct[a[ps]]) t.insert(ct[a[ps]]);
        if(ct[a[ps]]) st[ct[a[ps]]].insert(a[ps]);
        st[ct[x]].erase(x);
        if(st[ct[x]].empty()) t.erase(ct[x]);
        ct[x]++;
        if(st[ct[x]].empty()) if(*t.lower_bound(ct[x])!=ct[x]) t.insert(ct[x]);
        st[ct[x]].insert(x);
        a[ps]=x;
        auto p=--t.end();
        int lt=-1;
        c[0]=n+1;
        while(1){
            int pp=*p;
            if(*st[pp].begin()<c[nn]) c[++nn]=*st[pp].begin(),b[nn]=ct[c[nn]];
            if(p==t.begin()) break;
            --p;
        }
        reverse(b+1,b+nn+1);
        reverse(c+1,c+nn+1);
        for(auto tt:t){
            if(!tt) continue;
            int pp=*(--st[tt].end());
            int tp=lower_bound(b+1,b+nn+1,*(--t.end())-tt)-b;
            as=max(as,abs(pp-c[tp]));
        }
        cout<<as<<"\n";
    }
    return 0;
}