#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,q;
ll a[210000],m[210000];
ll d[2100],mi[2100],ma[2100];
ll cnt,ans;
map <ll,ll> c;
set <ll> s[210000];

void change(ll o,ll x){
	c[m[o]]--;
	if (c[m[o]]==0) c.erase(m[o]);
	s[m[o]].erase(o);
	m[o]--;
	c[m[o]]++;
	s[m[o]].insert(o);
	o=x;
	c[m[o]]--;
	if (c[m[o]]==0) c.erase(m[o]);
	s[m[o]].erase(o);
	m[o]++;
	c[m[o]]++;
	s[m[o]].insert(o);
}

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];
		m[a[i]]++;
	}
	for (int i=1;i<=n;i++){
		c[m[i]]++;
		s[m[i]].insert(i);
	}
	while (q--){
		ll id,x;
		cin>>id>>x;
		change(a[id],x);
		a[id]=x;
		for (int i=0;i<=2010;i++){
			d[i]=mi[i]=ma[i]=0;
		}
		cnt=ans=0;
		for (auto u:c){
			if (u.first!=0){
				d[++cnt]=u.first;
			}
		}
		for (int i=1;i<=cnt;i++){
			mi[i]=*s[d[i]].begin();
			ma[i]=*s[d[i]].rbegin();
		}
		for (int i=cnt-1;i>=1;i--){
			ma[i]=max(ma[i],ma[i+1]);
		}
		ll l=1,r=cnt;
		while (l<=cnt){
			while (r>=2&&d[r-1]+d[l]>=d[cnt]) r--;
			ans=max(ans,ma[r]-mi[l]);
			l++;
		}
		cout<<ans<<'\n';
	}
	return 0;
}