Problem:


Score : 1000 points

Problem Statement

There are N balls in a row.
Initially, the i-th ball from the left has the integer A_i written on it.

When Snuke cast a spell, the following happens:

Let the current number of balls be k. All the balls with k written on them disappear at the same time.

Snuke's objective is to vanish all the balls by casting the spell some number of times.
This may not be possible as it is. If that is the case, he would like to modify the integers on the minimum number of balls to make his objective achievable.

By the way, the integers on these balls sometimes change by themselves.
There will be M such changes. In the j-th change, the integer on the X_j-th ball from the left will change into Y_j.

After each change, find the minimum number of modifications of integers on the balls Snuke needs to make if he wishes to achieve his objective before the next change occurs. We will assume that he is quick enough in modifying integers. Here, note that he does not actually perform those necessary modifications and leaves them as they are.

Constraints

1 \leq N \leq 200000

1 \leq M \leq 200000

1 \leq A_i \leq N

1 \leq X_j \leq N

1 \leq Y_j \leq N

Subscore

In the test set worth 500 points, N \leq 200 and M \leq 200.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Output

Print M lines.
The j-th line should contain the minimum necessary number of modifications of integers on the balls to make Snuke's objective achievable.

Sample Input 1

5 3
1 1 3 4 5
1 2
2 5
5 4

Sample Output 1

0
1
1

After the first change, the integers on the balls become 2, 1, 3, 4, 5, from left to right. Here, all the balls can be vanished by casting the spell five times. Thus, no modification is necessary.

After the second change, the integers on the balls become 2, 5, 3, 4, 5, from left to right. In this case, at least one modification must be made. One optimal solution is to modify the integer on the fifth ball from the left to 2, and cast the spell four times.

After the third change, the integers on the balls become 2, 5, 3, 4, 4, from left to right. Also in this case, at least one modification must be made. One optimal solution is to modify the integer on the third ball from the left to 2, and cast the spell three times.

Sample Input 2

4 4
4 4 4 4
4 1
3 1
1 1
2 1

Sample Output 2

0
1
2
3

Sample Input 3

10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7

Sample Output 3

1
0
1
2
2
3
3
3
3
2



Sample input:
5 3
1 1 3 4 5
1 2
2 5
5 4


Sample output:
0
1
1

Submission status: Wrong Answer

Solution code:
input1 = list(map(int,input("").split(" ")))
A = list(map(int,input("").split(" ")))
N = input1[0]
M = input1[1]
temp = [ input() for _ in range(M) ]
XY = [None] * M
for i in range(M):
 	XY[i] = list(map(int,temp[i].split(" ")))

for j in range(M):
	A[XY[j][0]-1] = XY[j][1]
	sorted(A, reverse=True)
	magic = [None] * N
	for ball in A:
		index = 1
		while (ball-index) >= 0:
			if magic[ball-index] == None:
				magic[ball-index] = ball
				break
			elif magic[ball-index] == ball:
				index += 1
			else:
				break
	print(magic.count(None))

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,sys.stdin.readline().split())
E=N;c=[0]*300000;l=[0]*300000
A=list(map(int,sys.stdin.readline().split()))
def Z(e):
	global E
	p=e-c[e]
	c[e]+=1
	if p:
		if not l[p]: E-=1
		l[p]+=1
for e in A:Z(e)
A=[0]+A
for m in range(M):
	x,y=map(int,sys.stdin.readline().split())
	p=A[x]-c[A[x]]+1
	c[A[x]]-=1
	if p:
		l[p]-=1
		if not l[p]: E+=1
	A[x]=y
	Z(A[x])
	print(E)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

n, m = map(int, input().split())
an = list(map(int, input().split()))
ac = defaultdict(int, Counter(an))
ad = [0] * (n * 2)
for a, c in ac.items():
    for i in range(a - c, a):
        ad[i] += 1
ans = ad[:n].count(0)

for _ in range(m):
    x, y = map(int, input().split())
    ax = an[x - 1]
    xdi = ax - ac[ax]
    ad[xdi] -= 1
    ac[ax] -= 1
    ac[y] += 1
    ydi = y - ac[y]
    ad[ydi] += 1
    an[x - 1] = y
    if ad[xdi] == 0:
        ans += 1
    if ad[ydi] == 1:
        ans -= 1
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
if n > 200:exit()
a = map(int, raw_input().split())
for i in xrange(m):
    x, y = map(int, raw_input().split())
    x-=1
    a[x] = y
    nokori = n
    check = [False] * n
    ans = 0
    while nokori > 0:
        ok = False
        cnt = 0
        for j in xrange(n):
            if check[j]: continue
            if nokori == a[j]:
                check[j] = True
                ok = True
                cnt += 1
        if ok:
            nokori -= cnt
        else:
            ans += 1
            for j in xrange(n):
                if check[j]: continue
                if nokori < a[j]:
                    check[j] = True
                    nokori -= 1
                    ok = True
                    break
            if ok: continue
            else:
                for j in xrange(n):
                    if check[j]: continue
                    if nokori - 1 != a[j]:
                        check[j] = True
                        nokori -= 1
                        ok = True
                        break
                if ok:
                    continue
                else:
                    for j in xrange(n):
                        if check[j]: continue
                        if nokori == a[j]:
                            check[j] = True
                            nokori -= 1
                            break

    print ans

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,M = map(int,input().split())
arr = list(map(int,input().split()))

for i in range(M):
    X,Y = map(int,input().split())
    arr[X-1] = Y
    counter = Counter(arr)
    balls = N
    count = 0
    for n in range(N,0,-1):
        if n > balls: continue
        if balls in counter:
            balls -= counter[balls]
        else:
            count += 1
            balls -= 1
    print(count)

Submission status: Wrong Answer

Solution code:
# C
import numpy as np
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
res_list = []
cnt_list = np.zeros((N+1), dtype='int')
for A in A_list:
    cnt_list[A] += 1

AR = np.arange(N+1)

for _ in range(M):
    x, y = map(int, input().split())
    cnt_list[A_list[x-1]] -= 1
    cnt_list[y] += 1
    A_list[x-1] = y
    cnt_list_ = cnt_list.copy()
    
    res = 0
    
    p = N
    
    while p > 0:
        if cnt_list_[p] > 0:
            # greedy spell
            p_new = p - cnt_list_[p]
            cnt_list_[p] = 0
            p = p_new
        else:
            # find maximun nonzero
            if (np.cumsum(cnt_list_) > AR).sum() > 0:
                p0 = AR[np.cumsum(cnt_list_) > AR].min()
            elif cnt_list_[p:].sum() > 0:
                p0 = AR[cnt_list_ > 0].max()
            else:
                pass
                
            cnt_list_[p0] -= 1
            p -= 1
            res += 1
    res_list.append(res)
            
    
    
for res in res_list:
    print(res)

Submission status: Wrong Answer

Solution code:
# C
import numpy as np
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
res_list = []
cnt_list = np.zeros((N+1), dtype='int')
for A in A_list:
    cnt_list[A] += 1

AR = np.arange(N+1)

for _ in range(M):
    x, y = map(int, input().split())
    cnt_list[A_list[x-1]] -= 1
    cnt_list[y] += 1
    A_list[x-1] = y
    cnt_list_ = cnt_list.copy()
    
    res = 0
    
    p = N
    
    while p > 0:
        if cnt_list_[p] > 0:
            p_new = p - cnt_list_[p]
            cnt_list_[p] = 0
            p = p_new
        else:
            # find maximun nonzero
            if cnt_list_[p:].sum() > 0:
                p0 = AR[cnt_list_ > 0].max()
            else:
                p0 = AR[np.cumsum(cnt_list_) > AR].min()
            cnt_list_[p0] -= 1
            p -= 1
            res += 1
    res_list.append(res)
            
    
    
for res in res_list:
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""

N,M = 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 naive_solution(A):
    from collections import Counter
    covered = [False] * (N+N+10)
    for key,cnt in Counter(A).items():
        for i in range(cnt):
            covered[max(0,key-i)] = True
    return sum(not bl for bl in covered[1:N+1])

for x,y in XY:
    A[x-1] = y
    print(naive_solution(A))

Submission status: Time Limit Exceeded

Solution code:
n, m=map(int, raw_input().split())
a=map(int, raw_input().split())
for i in range(m):
	x, y=map(int, raw_input().split())
	a[x-1]=y
	cnt=[0]*(n+1)
	for j in a:
		cnt[j]+=1
	cover=[0]*(n+1)
	result=0
	for j in range(n+1):
		for k in range(min(cnt[j], j)):
			cover[j-k]+=1
	result+=cover.count(0)-1
	print result

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, m = map(int, input().split())
an = list(map(int, input().split()))
ac_ = Counter(an)
ac = {i: ac_[i] if i in ac_ else 0 for i in range(1, n + 1)}
ad = [0] * n
for a, c in ac.items():
    for i in range(max(0, a - c), a):
        ad[i] += 1
ans = ad.count(0)

for _ in range(m):
    x, y = map(int, input().split())
    ax = an[x - 1]
    xdi = ax - ac[ax]
    if xdi >= 0:
        ad[xdi] -= 1
        if ad[xdi] == 0:
            ans += 1
    ac[ax] -= 1
    ac[y] += 1
    ydi = y - ac[y]
    if ydi >= 0:
        ad[ydi] += 1
        if ad[ydi] == 1:
            ans -= 1
    an[x - 1] = y
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

n, m = map(int, input().split())
an = list(map(int, input().split()))
ac = defaultdict(int, Counter(an))
ad = [0] * (n * 2)
for a, c in ac.items():
    for i in range(a - c, a):
        ad[i] += 1
ans = ad[:n].count(0)

for _ in range(m):
    x, y = map(int, input().split())
    ax = an[x - 1]
    xdi = ax - ac[ax]
    ad[xdi] -= 1
    if xdi >= 0 and ad[xdi] == 0:
        ans += 1
    ac[ax] -= 1
    ac[y] += 1
    ydi = y - ac[y]
    ad[ydi] += 1
    if ydi >= 0 and ad[ydi] == 1:
        ans -= 1
    an[x - 1] = y
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

n, m = map(int, input().split())
an = list(map(int, input().split()))
ac = defaultdict(int, Counter(an))
ad = [0] * (n * 2)
for a, c in ac.items():
    for i in range(a - c, a):
        ad[i] += 1

for _ in range(m):
    x, y = map(int, input().split())
    ax = an[x - 1]
    ad[ax - ac[ax]] -= 1
    ac[ax] -= 1
    ac[y] += 1
    ad[y - ac[y]] += 1
    an[x - 1] = y
    print(ad[:n].count(0))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

# sys.stdin = open('c1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def vanish(p, details=False):
    while p:
        if details:
            print(p)
        n = len(p)
        q = [x for x in p if x != n]
        if len(q) == len(p):
            return False
        p = q[:]
    return True


def check(n):
    if n == 3:
        for i in range(1, n+1):
            for j in range(i, n+1):
                for k in range(j, n+1):
                    p = [i, j, k]
                    if vanish(p):
                        print(p)
                        # print()
                        # vanish(p, details=True)
    if n == 5:
        for i in range(1, n+1):
            for j in range(i, n+1):
                for k in range(j, n+1):
                    for l in range(k, n+1):
                        p = [i, j, k, l]
                        if vanish(p):
                            print(p)
                            # print()
                            # vanish(p, details=True)
    if n == 5:
        for i in range(1, n+1):
            for j in range(i, n+1):
                for k in range(j, n+1):
                    for l in range(k, n+1):
                        for m in range(l, n+1):
                            p = [i, j, k, l, m]
                            if vanish(p):
                                print(p)
                                # print()
                                # vanish(p, details=True)


def solve():
    # check(3)
    # check(4)
    # check(5)
    n, m = read_int_list()
    a = read_int_list()
    p = [read_int_list() for _ in range(m)]
    c = Counter(a)
    res = []
    for x, y in p:
        c[a[x-1]] -= 1
        a[x-1] = y
        c[a[x-1]] += 1
        covered = set(range(n))
        for i, ni in c.items():
            for j in range(i - ni, i):
                if j in covered:
                    covered.remove(j)
        r = len(covered)
        res.append(r)
    return '\n'.join(map(str, res))


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N,M = list(map(int,input().split()))

A = list(map(int,input().split()))

XY = [list(map(int,input().split())) for _ in range(M)]

counter = Counter(A)

for x,y in XY:
    counter[A[x-1]] -=1
    counter[y]+=1
    A[x-1]=y
    over = 0
    shotage = 0
    tmp = [0]*(N+1)
    tmp2 = 0
    #print(counter)
    for i in reversed(range(1,N+1)):
        assert tmp2 >=0
        if tmp2+counter[i]==0:
            shotage +=1
            tmp2+=1
        elif tmp2==1 and counter[i]==0:
            pass
        #elif tmp2==0 and counter[i]==1:
        #    tmp2+=1

        elif not tmp2:
            tmp2 += counter[i]

        elif tmp2 < counter[i]:
            over = tmp2
            tmp2  = counter[i]

        elif tmp2 >=counter[i]:
            over+=counter[i]

        tmp2 -=1
    #print(tmp,over,shotage)
    print(max(over,shotage))

Submission status: Accepted

Solution code:
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 = 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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""

N,M = 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 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)

Submission status: Accepted

Solution code:
n, m=map(int, raw_input().split())
a=map(int, raw_input().split())
cnt=[0]*(n+1)
for i in a:
	cnt[i]+=1
cover=[0]*(n+1)
for j in range(n+1):
	for k in range(min(cnt[j], j)):
		cover[j-k]+=1
result=cover.count(0)-1

for i in range(m):
	x, new=map(int, raw_input().split())
	old=a[x-1]
	a[x-1]=new
	cnt[old]-=1
	if cnt[old]<old:
		cover[old-cnt[old]]-=1
		if cover[old-cnt[old]]==0:
			result+=1
	if cnt[new]<new:
		if cover[new-cnt[new]]==0:
			result-=1
		cover[new-cnt[new]]+=1
	cnt[new]+=1
	print result
assert result==cover.count(0)-1
for j in range(n+1):
	for k in range(min(cnt[j], j)):
		cover[j-k]-=1
assert cover==[0]*(n+1)
for i in a:
	cnt[i]-=1
assert cnt==[0]*(n+1)

Submission status: Accepted

Solution code:
from collections import Counter
N,M = map(int,input().split())
A = list(map(int,input().split()))
src = [tuple(map(int,input().split())) for i in range(M)]
ctr = Counter(A)
cover = [0] * (2*N+1)
for k,v in ctr.items():
    for i in range(k,k-v,-1):
        cover[i+N] += 1
ans = cover[N+1:].count(0)

for x,y in src:
    ctr[A[x-1]] -= 1
    ai = A[x-1]+N - ctr[A[x-1]]
    cover[ai] -= 1
    if ai > N and cover[ai] == 0: ans += 1
    A[x-1] = y
    bi = y+N - ctr[y]
    if bi > N and cover[bi] == 0: ans -= 1
    cover[bi] += 1
    ctr[y] += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
N,M=map(int,sys.stdin.readline().split())
E=N;c=[0]*300000;l=[0]*300000
A=list(map(int,sys.stdin.readline().split()))
def Z(e):
	global E
	p=e-c[e]
	c[e]+=1
	if p>0:
		if not l[p]: E-=1
		l[p]+=1
for e in A:Z(e)
A=[0]+A
for m in range(M):
	x,y=map(int,sys.stdin.readline().split())
	p=A[x]-c[A[x]]+1
	c[A[x]]-=1
	if p>0:
		l[p]-=1
		if not l[p]: E+=1
	A[x]=y
	Z(A[x])
	print(E)

Submission status: Accepted

Solution code:
from collections import Counter

n, m = map(int, input().split())
an = list(map(int, input().split()))
ac_ = Counter(an)
ac = {i: ac_[i] if i in ac_ else 0 for i in range(1, n + 1)}
ad = [0] * n
for a, c in ac.items():
    for i in range(max(0, a - c), a):
        ad[i] += 1
ans = ad.count(0)
anss = []

for x, y in (map(int, input().split()) for _ in range(m)):
    ax = an[x - 1]
    xdi = ax - ac[ax]
    if xdi >= 0:
        ad[xdi] -= 1
        if ad[xdi] == 0:
            ans += 1
    ac[ax] -= 1
    ac[y] += 1
    ydi = y - ac[y]
    if ydi >= 0:
        ad[ydi] += 1
        if ad[ydi] == 1:
            ans -= 1
    an[x - 1] = y
    anss.append(ans)
print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

# sys.stdin = open('c1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def vanish(p, details=False):
    while p:
        if details:
            print(p)
        n = len(p)
        q = [x for x in p if x != n]
        if len(q) == len(p):
            return False
        p = q[:]
    return True


def check(n):
    if n == 3:
        for i in range(1, n + 1):
            for j in range(i, n + 1):
                for k in range(j, n + 1):
                    p = [i, j, k]
                    if vanish(p):
                        print(p)
                        # print()
                        # vanish(p, details=True)
    if n == 5:
        for i in range(1, n + 1):
            for j in range(i, n + 1):
                for k in range(j, n + 1):
                    for l in range(k, n + 1):
                        p = [i, j, k, l]
                        if vanish(p):
                            print(p)
                            # print()
                            # vanish(p, details=True)
    if n == 5:
        for i in range(1, n + 1):
            for j in range(i, n + 1):
                for k in range(j, n + 1):
                    for l in range(k, n + 1):
                        for m in range(l, n + 1):
                            p = [i, j, k, l, m]
                            if vanish(p):
                                print(p)
                                # print()
                                # vanish(p, details=True)


def solve_small():
    # check(3)
    # check(4)
    # check(5)
    n, m = read_int_list()
    a = read_int_list()
    p = [read_int_list() for _ in range(m)]
    c = Counter(a)
    res = []
    for x, y in p:
        c[a[x - 1]] -= 1
        a[x - 1] = y
        c[a[x - 1]] += 1
        covered = set(range(n))
        for i, ni in c.items():
            for j in range(i - ni, i):
                if j in covered:
                    covered.remove(j)
        r = len(covered)
        res.append(r)
    return '\n'.join(map(str, res))


def solve():
    n, m = read_int_list()
    a = read_int_list()
    p = [read_int_list() for _ in range(m)]
    c = Counter(a)
    covered = Counter({i: 0 for i in range(n)})
    for i, ni in c.items():
        for j in range(i - ni, i):
            if 0 <= j:
                covered[j] += 1
    r = 0
    for i, v in covered.items():
        if 0 <= i:
            if v == 0:
                r += 1
    res = []
    for x, y in p:
        x -= 1
        i = a[x] - c[a[x]]
        covered[i] -= 1
        if 0 <= i:
            if covered[i] == 0:
                r += 1
        c[a[x]] -= 1
        a[x] = y
        c[a[x]] += 1
        i = a[x] - c[a[x]]
        if 0 <= i:
            if covered[i] == 0:
                r -= 1
        covered[i] += 1
        res.append(r)
    return '\n'.join(map(str, res))


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    a = map(int, stdin.readline().split(), repeat(10, n))
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    f = [0] * (n + 1)
    g = [0] * (n + 1)
    for x in a:
        if x - f[x] >= 1:
            g[x-f[x]] += 1
        f[x] += 1
    ans = sum(not x for x in g) - 1
    p = []
    for i in xrange(m):
        x, y = dat[i*2], dat[i*2+1]
        x -= 1
        f[a[x]] -= 1
        if a[x] - f[a[x]] >= 1:
            g[a[x]-f[a[x]]] -= 1
            if not g[a[x]-f[a[x]]]:
                ans += 1
        a[x] = y
        if y - f[y] >= 1:
            if not g[y-f[y]]:
                ans -= 1
            g[y-f[y]] += 1
        f[y] += 1
        p.append(ans)
    print "\n".join("%i" % x for x in p)
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

"""
・とりあえず部分点解法：各クエリに対してO(N)
・いくつかを残していくつかを自由に埋める
・残すもの：被覆区間がoverlapしないように残す
・つまり、区間で覆えている点が処理できて、区間で覆えていない点が他所から持ってこないといけない。
"""

N,M = 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 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]))

if N <= 200 and M <= 200:
    subscore_solution()
    exit()

raise Exception