#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(n), c(n);
    int r = n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;

        int k = a[i] - b[a[i]]++;
        if (k >= 0) r -= c[k]++ == 0;
    }
    

    for (int j = 0; j < m; j++) {
        int x, y, k;
        cin >> x >> y;
        x--; y--;

        k = y - b[y]++;
        if (k >= 0) r -= c[k]++ == 0;

        k = a[x] - --b[a[x]];
        if (k >= 0) r += --c[k] == 0;

        a[x] = y;

        cout << r << '\n';
    }

    return 0;
}