#include<bits/stdc++.h>
using namespace std;
const int N=200005;

int n,q;
int a[N],m[N],cnt;
int d[N],mn[N],mx[N];
map<int,int>mp;
set<int>st[N];

void add(int x,int v)
{
	mp[m[x]]--;
	if(!mp[m[x]])mp.erase(m[x]);
	st[m[x]].erase(x);
	m[x]+=v;
	mp[m[x]]++;
	st[m[x]].insert(x);
}

int main()
{
	freopen("Queries.in","r",stdin);
	freopen("Queries.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>q;
	for(int i=1;i<=n;++i){cin>>a[i];m[a[i]]++;}
	for(int i=1;i<=n;++i){mp[m[i]]++;st[m[i]].insert(i);}
	while(q--){
		int p,x;cin>>p>>x;
		add(a[p],-1);
		a[p]=x;
		add(a[p],1);
		cnt=0;
		for(auto it:mp)if(it.first)d[++cnt]=it.first;
		int k=d[cnt];
		for(int i=1;i<=cnt;++i){
			mn[i]=*st[d[i]].begin();
			mx[i]=*st[d[i]].rbegin();
		}
		for(int i=cnt-1;i;--i)mx[i]=max(mx[i],mx[i+1]);
		int ans=0;
		for(int l=1,r=cnt;l<=cnt;++l){
			while(r>1&&d[r-1]+d[l]>=k)r--;
			ans=max(ans,mx[r]-mn[l]);
		}
		cout<<ans<<"\n";
	}
	return 0;
}