#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;


struct SegT {
private:
	int n; vector<int> node, lazy;
	const int init_c = mod;
public:
	int f(int a, int b) {
		return min(a, b);
	}
	void init(vector<int> a) {
		int sz = a.size();
		n = 1;
		while (n < sz)n <<= 1;
		node.resize(2 * n - 1, init_c);
		lazy.resize(2 * n - 1, 0);
		rep(i, a.size()) {
			node[i + n - 1] = a[i];
		}
		per(i, n - 1) {
			node[i] = f(node[2 * i + 1], node[2 * i + 2]);
		}
	}
	void eval(int k, int l, int r) {
		node[k] += lazy[k];
		if (r - l > 1) {
			lazy[2 * k + 1] += lazy[k];
			lazy[2 * k + 2] += lazy[k];
		}
		lazy[k] = 0;
	}
	void add(int x, int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return;
		if (a <= l && r <= b) {
			lazy[k] += x; eval(k, l, r);
		}
		else {
			add(x, a, b, k * 2 + 1, l, (l + r) / 2);
			add(x, a, b, k * 2 + 2, (l + r) / 2, r);
			node[k] = f(node[k * 2 + 1], node[k * 2 + 2]);
		}
	}
	int query(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return init_c;
		if (a <= l && r <= b)return node[k];
		else {
			int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
			int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
			return f(vl, vr);
		}
	}
	int locsearch(int a, int b, int key, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		eval(k, l, r);
		if (r <= a || b <= l)return -1;
		if (node[k] > key)return -1;
		else if (r - l == 1)return k - (n - 1);
		else {
			int vr = locsearch(a, b,key, k * 2 + 2, (l + r) / 2, r);
			if (vr >= 0)return vr;
			int vl = locsearch(a, b,key, k * 2 + 1, l, (l + r) / 2);
			return vl;
		}
	}
	int searchloc(int ri,int key) {
		return locsearch(0, ri, key);
		/*int le = -1, rri = ri;
		while (rri - le > 1) {
			int mid = (rri + le) / 2;
			int z = query(mid, ri);
			if (z <= key) {
				le = mid;
			}
			else {
				rri = mid;
			}
		}
		return le;*/
	}
};

vector<int> c;
int calc(vector<int> &a) {
	int s = 0; int ret = 0;
	per(i, a.size()) {
		c[i] = s - c[i];
		ret += min(a[i], s);
		s = max(a[i], s);
		s = max(0, s - 1);
	}
	return ret;
}

SegT st;
int b[1 << 18]; int ans;
vector<int> a;
void add(int t) {
	int z = st.query(t, t + 1);
	if (z > 0) {
		ans++; 
		st.add(-1, t, t + 1);
	}
	else {
		int loc = st.searchloc(t, -1);
		if (t - loc <= a[t]) {
			ans++;
			st.add(1, loc, t);
			st.add(-1, t, t + 1);
		}
		else {
			st.add(1, t - a[t], t);
			st.add(-1, t, t + 1);
		}
	}
}
void del(int t) {
	int z = st.query(t, t + 1);
	//cout << "hsv " << z << endl;
	if (z >= 0) {
		ans--;
		st.add(1, t, t + 1);
	}
	else {
		int loc = st.searchloc(t, 0);
		//cout << "hello " << loc << endl;
		if (t - loc < a[t]) {
			ans--;
			st.add(-1, loc, t);
			st.add(1, t, t + 1);
		}
		else {
			st.add(-1, t - a[t] + 1, t);
			st.add(1, t, t + 1);
		}
	}
}
int main() {
	int n, m; cin >> n >> m;
	a.resize(n + 1, 0);
	a[0] = 300000;
	rep(i, n) {
		cin >> b[i]; a[b[i]]++;
	}
	c = a;
	ans=calc(a); st.init(c);
	/*rep(i, n + 1) {
		cout << c[i] << endl;
	}*/
	//cout << ans << endl;
	rep(i, m) {
		int x, y; cin >> x >> y;
		del(b[x - 1]);
		a[b[x - 1]]--; 
		//cout << "hel"<<ans << endl;
		b[x - 1] = y; 
		add(y);
		a[y]++;
		cout << ans << endl;
	}
	//stop
	return 0;
}


Measured memory_bytes: 9328