#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    char c=getchar();
    int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=200010;
int n,q;
int a[N],t[N];
set<int> pz;
set<int> apr[N];
int main()
{
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
    n=re();q=re();
    for(int i=1;i<=n;i++) a[i]=re(),t[a[i]]++;
    for(int i=1;i<=n;i++) if(t[i]) pz.insert(t[i]),apr[t[i]].insert(i);
    for(int i=1;i<=q;i++)
    {
        int p=re(),z=re();
        apr[t[a[p]]].erase(a[p]);
        if(apr[t[a[p]]].size()==0) pz.erase(t[a[p]]);
        t[a[p]]--;
        if(t[a[p]])
        {
            apr[t[a[p]]].insert(a[p]);
            pz.insert(t[a[p]]);
        }
        a[p]=z;
        if(t[a[p]])
        {
            apr[t[a[p]]].erase(a[p]);
            if(apr[t[a[p]]].size()==0) pz.erase(t[a[p]]);
        }
        t[a[p]]++;
        apr[t[a[p]]].insert(a[p]);
        pz.insert(t[a[p]]);
        
//        cout<<"check"<<endl;
//        cout<<pz.size()<<' ';for(int x:pz) cout<<x<<' ';cout<<endl;
        
        int ans=0;
        auto pr=pz.begin(),pl=pz.end();
        pl--;int lim=(*pl);
        int nowl=*apr[*pl].begin(),nowr=*(--apr[*pl].end());
        for(;pr!=pz.end();pr++)
        {
            while(pl!=pz.begin())
            {
                auto tmp=pl;tmp--;
                if((*pr)+(*tmp)>=lim) pl--,nowl=min(nowl,*apr[*pl].begin()),nowr=max(nowr,*(--apr[*pl].end()));
                else break;
            }
            ans=max({ans,(*(--apr[*pr].end()))-nowl,nowr-(*apr[*pr].begin())});
        }
        printf("%d\n",ans);
    }
    return 0;
}