#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3010,inf=1e9;
int n,q,a[N],cnt[N];
ll getans () {
    int m=0;
    for (int i=1;i<=n;i++) m=max(m,cnt[i]);
    ll mn[N],mx[N],smn[N],smx[N];
    for (int i=1;i<=n+1;i++) {
        mn[i]=smn[i]=inf;
        mx[i]=smx[i]=-inf;
    }
    for (ll i=1;i<=n;i++) {
        int w=cnt[i];
        mn[w]=min(mn[w],i);
        mx[w]=max(mx[w],i);
    }
    for (int w=n;w>=1;w--) {
        smn[w]=min(smn[w+1],mn[w]);
        smx[w]=max(smx[w+1],mx[w]);
    }
    ll ans=0;
    for (int i=1;i<=m;i++) {
        if (mn[i]==inf) continue;
        int t=max(1,m-i);
        ans=max(ans,smx[t]-mn[i]);
        ans=max(ans,mx[i]-smn[t]);
    }
    return ans;
}
int main () {
    freopen("Queries.in","r",stdin);
    freopen("Queries.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> q;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    while (q--) {
        int x,y;
        cin >> x >> y;
        cnt[a[x]]--;
        cnt[y]++;
        a[x]=y;
        cout << getans() <<endl;
    }
    return 0;
}