#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, q;
int a[200010];

int cnt[200010];
int nur[200010];
int ans;

void Add(int i){
	++cnt[i];
	if(i-cnt[i]>=0) ans -= !nur[i-cnt[i]]++;
}

void Rem(int i){
	if(i-cnt[i]>=0) ans += !--nur[i-cnt[i]];
	--cnt[i];
}

int main()
{
	read(n, q); ans=n;
	for(int i=1; i<=n; ++i) read(a[i]), Add(a[i]);
	for(;q--;){
		int x, y; read(x, y);
		Rem(a[x]); Add(a[x]=y);
		printf("%d\n", ans);
	}
	return 0;
}
