#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (int)(1e18)

const int N=2e5+10;

int n,q;
int a[N],val[N],nxt[N],las[N];

set<int> s[N];

//只身山水间 耳不闻恶语闲言
//举头问苍天 何时得以赴黄泉 

inline int read(){
    int t=0,f=1;
    register char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?(-1):(f),c=getchar();
    while(c>='0'&&c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
    return t*f;
}

void ins(int x,int v){
    if(s[x].empty()&&x){
        if(!s[x+1].empty()) nxt[x]=x+1,las[x]=las[x+1],nxt[las[x]]=x,las[x+1]=x;
        else nxt[x]=nxt[x-1],las[x]=x-1,nxt[x-1]=x,las[nxt[x]]=x;
    }
    s[x].insert(v);
}

void del(int x,int v){
    s[x].erase(v);
    if(s[x].empty()&&x) nxt[las[x]]=nxt[x],las[nxt[x]]=las[x];
}

signed main(){
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read(),val[a[i]]++;
    for(int i=1;i<=n;i++){
        if(!val[i]) continue;
        s[val[i]].insert(i);
    }
    int last=0;
    for(int i=1;i<=n;i++){
        if(s[i].empty()) continue;
        las[i]=last,nxt[last]=i,last=i;
    }
    nxt[last]=n+1,las[n+1]=last;
//    for(int i=nxt[0];i!=n+1;i=nxt[i]){
//            cout<<"i:"<<i<<" s:"<<s[i].size()<<" min:"<<(*s[i].begin())<<" max:"<<(*--s[i].end())<<"\n";
//        }
    while(q--){
        int x=read(),v=read();
        ins(val[a[x]]-1,a[x]);del(val[a[x]],a[x]);
        val[a[x]]--,a[x]=v,val[a[x]]++;
        ins(val[a[x]],a[x]);del(val[a[x]]-1,a[x]);
//        for(int i=nxt[0];i!=n+1;i=nxt[i]){
//            cout<<"i:"<<i<<" s:"<<s[i].size()<<" min:"<<(*s[i].begin())<<" max:"<<(*--s[i].end())<<"\n";
//        }
        int maxv=las[n+1],maxp=0,minp=n+1,ans=0;
        for(int l=nxt[0],r=las[n+1];l!=n+1;l=nxt[l]){
            while(r&&l+r>=maxv) maxp=max(maxp,*(--s[r].end())),minp=min(minp,*s[r].begin()),r=las[r];
//            cout<<"l:"<<l<<" r:"<<r<<"\n";
            ans=max(ans,abs(maxp-(*s[l].begin()))),ans=max(ans,abs(minp-(*--s[l].end())));
        }
        cout<<ans<<"\n";
    }
    return 0;
}