import sys

input = sys.stdin.readline



"""

・とりあえず部分点解法：各クエリに対してO(N)

・いくつかを残していくつかを自由に埋める

・残すもの：被覆区間がoverlapしないように残す

・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。

"""



N,M = list(map(int,input().split()))

A = [int(x) for x in input().split()]

XY = [tuple(int(x) for x in input().split()) for _ in range(M)]



def subscore_solution():

    from collections import Counter

    for x,y in XY:

        A[x-1] = y

        covered = [False] * (N+N+10)

        for key,cnt in list(Counter(A).items()):

            for i in range(cnt):

                covered[max(0,key-i)] = True

        print((sum(not bl for bl in covered[1:N+1])))



counter = [0] * (N+1)

covered = [0] * (N+N+10)

for a in A:

    counter[a] += 1

    covered[a-counter[a]+1] += 1

magic = sum(x==0 for x in covered[1:N+1])



for i,y in XY:

    x = A[i-1]

    A[i-1] = y

    rem = x - counter[x] + 1

    counter[x] -= 1

    counter[y] += 1

    add = y - counter[y] + 1

    covered[rem] -= 1

    if 1<=rem<=N and covered[rem] == 0:

        magic += 1

    if 1<=add<=N and covered[add] == 0:

        magic -= 1

    covered[add] += 1

    print(magic)



import sys

import numpy as np



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



def main(A, X, Y):

    N = len(A)

    count = np.zeros(N + 1, np.int64)

    covered = np.zeros(N + 1, np.int64)

    for x in A:

        count[x] += 1

        y = x - count[x] + 1

        if y > 0:

            covered[y] += 1

    spell = np.sum(covered[1:] == 0)

    for i in range(len(X)):

        x, y = X[i], Y[i]

        before = A[x - 1]

        after = y

        A[x - 1] = y

        rem = before - count[before] + 1

        count[before] -= 1

        add = after - count[after]

        count[after] += 1

        if rem > 0:

            covered[rem] -= 1

            if not covered[rem]:

                spell += 1

        if add > 0:

            if not covered[add]:

                spell -= 1

            covered[add] += 1

        print(spell)



if sys.argv[-1] == 'ONLINE_JUDGE':

    import numba

    from numba.pycc import CC

    i8 = numba.from_dtype(np.int64)

    signature = (i8[:], i8[:], i8[:])



    cc = CC('my_module')

    cc.export('main', signature)(main)

    cc.compile()



from my_module import main



N, M = list(map(int, readline().split()))

A = np.array(readline().split(), np.int64)

XY = np.array(read().split(), np.int64)

X = XY[::2]

Y = XY[1::2]



main(A, X, Y)
import sys

input = sys.stdin.readline
"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""
N, M = list(map(int, input().split()))
A = [int(x) for x in input().split()]
XY = [tuple(int(x) for x in input().split()) for _ in range(M)]


def subscore_solution():
    from collections import Counter

    for x, y in XY:
        A[x - 1] = y
        covered = [False] * (N + N + 10)
        for key, cnt in list(Counter(A).items()):
            for i in range(cnt):
                covered[max(0, key - i)] = True
        print((sum(not bl for bl in covered[1 : N + 1])))


counter = [0] * (N + 1)
covered = [0] * (N + N + 10)
for a in A:
    counter[a] += 1
    covered[a - counter[a] + 1] += 1
magic = sum(x == 0 for x in covered[1 : N + 1])
for i, y in XY:
    x = A[i - 1]
    A[i - 1] = y
    rem = x - counter[x] + 1
    counter[x] -= 1
    counter[y] += 1
    add = y - counter[y] + 1
    covered[rem] -= 1
    if 1 <= rem <= N and covered[rem] == 0:
        magic += 1
    if 1 <= add <= N and covered[add] == 0:
        magic -= 1
    covered[add] += 1
    print(magic)

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main(A, X, Y):
    N = len(A)
    count = np.zeros(N + 1, np.int64)
    covered = np.zeros(N + 1, np.int64)
    for x in A:
        count[x] += 1
        y = x - count[x] + 1
        if y > 0:
            covered[y] += 1
    spell = np.sum(covered[1:] == 0)
    for i in range(len(X)):
        x, y = X[i], Y[i]
        before = A[x - 1]
        after = y
        A[x - 1] = y
        rem = before - count[before] + 1
        count[before] -= 1
        add = after - count[after]
        count[after] += 1
        if rem > 0:
            covered[rem] -= 1
            if not covered[rem]:
                spell += 1
        if add > 0:
            if not covered[add]:
                spell -= 1
            covered[add] += 1
        print(spell)


if sys.argv[-1] == "ONLINE_JUDGE":
    import numba
    from numba.pycc import CC

    i8 = numba.from_dtype(np.int64)
    signature = (i8[:], i8[:], i8[:])
    cc = CC("my_module")
    cc.export("main", signature)(main)
    cc.compile()
from my_module import main

N, M = list(map(int, readline().split()))
A = np.array(readline().split(), np.int64)
XY = np.array(read().split(), np.int64)
X = XY[::2]
Y = XY[1::2]
main(A, X, Y)

+import numpy as np -input = sys.stdin.readline -""" -・とりあえず部分点解法：各クエリに対してO(N) -・いくつかを残していくつかを自由に埋める -・残すもの：被覆区間がoverlapしないように残す -・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。 -""" -N, M = list(map(int, input().split())) -A = [int(x) for x in input().split()] -XY = [tuple(int(x) for x in input().split()) for _ in range(M)] +read = sys.stdin.buffer.read +readline = sys.stdin.buffer.readline +readlines = sys.stdin.buffer.readlines -def subscore_solution(): -    from collections import Counter - -    for x, y in XY: +def main(A, X, Y): +    N = len(A) +    count = np.zeros(N + 1, np.int64) +    covered = np.zeros(N + 1, np.int64) +    for x in A: +        count[x] += 1 +        y = x - count[x] + 1 +        if y > 0: +            covered[y] += 1 +    spell = np.sum(covered[1:] == 0) +    for i in range(len(X)): +        x, y = X[i], Y[i] +        before = A[x - 1] +        after = y -        covered = [False] * (N + N + 10) -        for key, cnt in list(Counter(A).items()): -            for i in range(cnt): -                covered[max(0, key - i)] = True -        print((sum(not bl for bl in covered[1 : N + 1]))) +        rem = before - count[before] + 1 +        count[before] -= 1 +        add = after - count[after] +        count[after] += 1 +        if rem > 0: +            covered[rem] -= 1 +            if not covered[rem]: +                spell += 1 +        if add > 0: +            if not covered[add]: +                spell -= 1 +            covered[add] += 1 +        print(spell) -counter = [0] * (N + 1) -covered = [0] * (N + N + 10) -for a in A: -    counter[a] += 1 -    covered[a - counter[a] + 1] += 1 -magic = sum(x == 0 for x in covered[1 : N + 1]) -for i, y in XY: -    x = A[i - 1] -    A[i - 1] = y -    rem = x - counter[x] + 1 -    counter[x] -= 1 -    counter[y] += 1 -    add = y - counter[y] + 1 -    covered[rem] -= 1 -    if 1 <= rem <= N and covered[rem] == 0: -        magic += 1 -    if 1 <= add <= N and covered[add] == 0: -        magic -= 1 -    covered[add] += 1 -    print(magic) +if sys.argv[-1] == "ONLINE_JUDGE": +    import numba +    from numba.pycc import CC + +    i8 = numba.from_dtype(np.int64) +    signature = (i8[:], i8[:], i8[:]) +    cc = CC("my_module") +    cc.export("main", signature)(main) +    cc.compile() +from my_module import main + +N, M = list(map(int, readline().split())) +A = np.array(readline().split(), np.int64) +XY = np.array(read().split(), np.int64) +X = XY[::2] +Y = XY[1::2] +main(A, X, Y)