#include <bits/stdc++.h>
using namespace std;
const int N=8e5+10,mod=1e9+7;
int n,q,a[N],mp[N],tot=0,mi[N],mx[N];
set<int> s[N];
void solve()
{
    cin>>n>>q;mi[n+1]=1e9;
    for (int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
    for (int i=1;i<=n;i++) s[mp[i]].insert(i);
    while (q--)
    {
        int x,y;
        cin>>x>>y;
        s[mp[a[x]]].erase(a[x]),mp[a[x]]--,s[mp[a[x]]].insert(a[x]);
        s[mp[y]].erase(y),mp[y]++,s[mp[y]].insert(y);//        cout<<1<<endl;
        a[x]=y;
        int qmx=0;
        for (int i=n;i>=1;i--)
        {
            mi[i]=mi[i+1],mx[i]=mx[i+1];
            if (!s[i].empty())
            {
                mi[i]=min(mi[i],*s[i].begin());
                auto it=s[i].end();it--;
                mx[i]=max(mx[i],*it);
                if (!qmx) qmx=i;
            }
        }
        int ans=0;
        for (int i=qmx;i>=1;i--)
        {
            if (s[i].empty()) continue;
            auto it=s[i].end();it--;
            int cnt=max(1,qmx-i);
            ans=max(ans,max(*it-mi[cnt],mx[cnt]-*s[i].begin()));
        }
        cout<<ans<<"\n";
    }
}
int main() {
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}