#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
typedef long long ll;

const int MAX_N=2e5,MAX_M=2e5;

int N,M,A[MAX_N];

int n[MAX_N],ovr[MAX_N];

int main(){
	cin>>N>>M;
	REP(i,N){
		cin>>A[i];
		n[A[i]-1]++;
	}
	REP(i,N){
		REP(j,n[i]){
			if (i-j>=0){
				ovr[i-j]++;
			}
		}
	}
	int ans=0;
	REP(i,N){
		if (ovr[i]==0){
			ans++;
		}
	}
	REP(i,M){
		int x,y;
		cin>>x>>y;
		x--;
		int w=A[x];
		if (w-n[w-1]>=0 && --ovr[w-n[w-1]]==0){
			ans++;
		}
		n[w-1]--;
		n[y-1]++;
		if (y-n[y-1]>=0 && ovr[y-n[y-1]]++==0){
			ans--;
		}
		A[x]=y;
		cout<<ans<<endl;
	}
	return 0;
}