#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, q, cnt, A[N], C[N], M[N];
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]), C[A[i]] ++;
    for (int i = 1; i <= n; i++)
        for (int j = i; j > max(i - C[i], 0); j--)
            M[j] ++;
    for (int i = 1; i <= n; i++)
        if (!M[i])
            cnt ++;
    for (; q; q --)
    {
        int id, a;
        scanf("%d%d", &id, &a);
        C[A[id]] --;
        if (A[id] - C[A[id]] >= 1)
            M[A[id] - C[A[id]]] --, cnt += !M[A[id] - C[A[id]]];
        A[id] = a;
        if (a - C[a] >= 1)
            cnt -= !M[a - C[a]], M[a - C[a]] ++;
        C[a] ++;
        printf("%d\n", cnt);
    }
    return 0;
}