#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000;
int n, m, a[maxn + 10], cnt[maxn + 10], cov[maxn + 10], ans;

void modify(int p, int v) {
	if (p >= 1) {
		ans -= !!cov[p];
		ans += !!(cov[p] += v);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		modify(a[i] - (cnt[a[i]]++), 1);
	}
	while (m--) {
		int x, y; scanf("%d%d", &x, &y);
		modify(a[x] - (--cnt[a[x]]), -1);
		a[x] = y;
		modify(y - (cnt[y]++), 1);
		printf("%d\n", n - ans);
	}
}
