问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.
Respond to the following Q queries in the order they are given.
The k-th query is given in the following format:
i_k x_k


- First, change A_{i_k} to x_k. This change will carry over to subsequent queries.
- Then, print the \rm{mex} of A.
- The \rm{mex} of A is the smallest non-negative integer not contained in A.

Input

Input is given from Standard Input in the following format:
N Q
A_1 A_2 \dots A_N
i_1 x_1
i_2 x_2
\vdots
i_Q x_Q

Output

Print Q lines in total.
The k-th line should contain the answer to the k-th query as an integer.

Constraints


- All input values are integers.
- 1 \le N,Q \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 1 \le i_k \le N
- 0 \le x_k \le 10^9

Sample Input 1

8 5
2 0 2 2 1 1 2 5
4 3
4 4
6 3
8 1000000000
2 1

Sample Output 1

4
3
6
5
0

Initially, the sequence A is (2,0,2,2,1,1,2,5).
This input gives you five queries.

- The first query changes A_4 to 3, making A=(2,0,2,3,1,1,2,5).
- At this point, the \rm{mex} of A is 4.


- The second query changes A_4 to 4, making A=(2,0,2,4,1,1,2,5).
- At this point, the \rm{mex} of A is 3.


- The third query changes A_6 to 3, making A=(2,0,2,4,1,3,2,5).
- At this point, the \rm{mex} of A is 6.


- The fourth query changes A_8 to 1000000000, making A=(2,0,2,4,1,3,2,1000000000).
- At this point, the \rm{mex} of A is 5.


- The fifth query changes A_2 to 1, making A=(2,1,2,4,1,3,2,1000000000).
- At this point, the \rm{mex} of A is 0.

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
Q = int(data[1])
A = list(map(int, data[2:2+N]))
queries = []
for i in range(Q):
queries.append((int(data[2+N+2*i]), int(data[2+N+2*i+1])))

# Initialize the set of potential mex values
mex_set = set(range(N+1))
for a in A:
mex_set.discard(a)

# Find the initial mex
mex = min(mex_set)

results = []
for i, x in queries:
# Update the mex_set based on the current value at A[i-1]
if A[i-1] in mex_set:
mex_set.add(A[i-1])
# Update A[i-1] to x
A[i-1] = x
# Update the mex_set based on the new value x
mex_set.discard(x)
# Recalculate mex
mex = min(mex_set)
results.append(mex)

sys.stdout.write('\n'.join(map(str, results)) + '\n')
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
deepseek-r1

```python
import sys

def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
N = int(data[idx])
idx += 1
Q = int(data[idx])
idx += 1
A = list(map(int, data[idx:idx+N]))
idx += N

max_m = N
freq = [0] * (max_m + 1)
for x in A:
if x <= max_m:
freq[x] += 1

# Initialize the segment tree
size = 1
while size < (max_m + 1):
size <<= 1
covered = [False] * (2 * size)

# Function to update the segment tree
def update(m, present):
node = size + m
if covered[node] == present:
return
covered[node] = present
node >>= 1
while node >= 1:
left = node << 1
right = left + 1
new_covered = covered[left] and covered[right]
if covered[node] == new_covered:
break
covered[node] = new_covered
node >>= 1

# Initialize the segment tree based on initial freq
for m in range(max_m + 1):
if freq[m] > 0:
update(m, True)

# Query function to find mex
def query():
node = 1
l = 0
r = size - 1
while l < r:
mid = (l + r) // 2
left_node = node << 1
right_node = left_node + 1
if not covered[left_node]:
r = mid
node = left_node
else:
l = mid + 1
node = right_node
return l

# Process each query
for _ in range(Q):
i = int(data[idx]) - 1
idx += 1
x = int(data[idx])
idx += 1
old_val = A[i]
new_val = x

# Process old_val
if old_val <= max_m:
freq[old_val] -= 1
if freq[old_val] == 0:
update(old_val, False)

# Process new_val
if new_val <= max_m:
if freq[new_val] == 0:
update(new_val, True)
freq[new_val] += 1

A[i] = new_val

# Query and output mex
print(query())

if __name__ == '__main__':
main()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE

import sys
import threading
import heapq

def main():
import sys

sys.setrecursionlimit(1 << 25)

N, Q = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
counts = [0]*(N+2) # counts[0..N+1]
missing_numbers = []
for x in A:
if x <= N:
counts[x] +=1
# Build the missing_numbers heap with counts[x]==0
missing_numbers = []
for x in range(N+2):
if counts[x]==0:
heapq.heappush(missing_numbers, x)
for _ in range(Q):
while True:
s = sys.stdin.readline()
if s.strip() != '':
break
i_k_str, x_k_str = s.strip().split()
i_k = int(i_k_str) -1
x_k = int(x_k_str)
old_x = A[i_k]
A[i_k] = x_k
if old_x <= N:
counts[old_x] -=1
if counts[old_x]==0:
heapq.heappush(missing_numbers, old_x)
if x_k <= N:
if counts[x_k]==0:
# We don't remove x_k from missing_numbers heap yet
pass
counts[x_k] +=1

# Output mex
while True:
x = missing_numbers[0]
if counts[x]==0:
print(x)
break
else:
heapq.heappop(missing_numbers)

threading.Thread(target=main).start()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
import sys
input = sys.stdin.read

def find_mex(A):
# Use a set to track the numbers in A
present = set(A)
# Start checking from 0 upwards
mex = 0
while mex in present:
mex += 1
return mex

def main():
data = input().split()
N = int(data[0])
Q = int(data[1])

A = list(map(int, data[2:N+2]))
queries = data[N+2:]

results = []

for q in range(Q):
i_k = int(queries[2*q]) - 1 # Convert to 0-based index
x_k = int(queries[2*q + 1])

# Update the array
A[i_k] = x_k

# Calculate the mex
mex = find_mex(A)

# Store the result
results.append(mex)

# Print all results
for result in results:
print(result)

main()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
import sys

# Read input
N, Q = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

# Process each query
for _ in range(Q):
i_k, x_k = map(int, sys.stdin.readline().split())
# Update the sequence A
A[i_k - 1] = x_k
# Find the mex of the sequence A
present = set(A)
mex = 0
while mex in present:
mex += 1
# Print the mex
print(mex)
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys
input = sys.stdin.readline

def solve():
n, q = map(int, input().split())
a = list(map(int, input().split()))
cnt = [0] * (n + 1)
for i in a:
if i <= n:
cnt[i] += 1
mex = 0
while cnt[mex]:
mex += 1
for _ in range(q):
i, x = map(int, input().split())
i -= 1
if a[i] <= n:
cnt[a[i]] -= 1
if a[i] < mex:
while cnt[mex - 1]:
mex -= 1
a[i] = x
if x <= n:
cnt[x] += 1
if x < mex:
while cnt[mex]:
mex += 1
print(mex)

if __name__ == '__main__':
solve()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys
from collections import defaultdict

def input():
return sys.stdin.readline().strip()

def solve():
n, q = map(int, input().split())
a = list(map(int, input().split()))
cnt = defaultdict(int)
for x in a:
cnt[x] += 1
mex = 0
while cnt[mex] > 0:
mex += 1
for _ in range(q):
i, x = map(int, input().split())
i -= 1
cnt[a[i]] -= 1
if cnt[a[i]] == 0 and a[i] < mex:
mex = a[i]
a[i] = x
cnt[a[i]] += 1
while cnt[mex] > 0:
mex += 1
print(mex)

solve()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
from bisect import bisect_left

N, Q = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
mex = 0
for i in range(N):
if A[i] == mex:
mex += 1
else:
break

for _ in range(Q):
i, x = map(int, input().split())
i -= 1
a = A[i]
idx = bisect_left(A, a)
A[i] = x
if a == mex and mex < N:
mex += 1
while mex < N and mex == A[bisect_left(A, mex)]:
mex += 1
idx = bisect_left(A, x)
if idx == N or A[idx] != x:
while mex < N and mex == A[bisect_left(A, mex)]:
mex += 1
print(mex)
```

```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
baichuan4 ```python
from collections import defaultdict

def mex(A):
# Create a set for faster lookups
A_set = set(A)
# Find the smallest non-negative integer not in A
for i in range(len(A)):
if i not in A_set:
return i
return len(A)

# Read the first line of input
N, Q = map(int, input().split())

# Read the sequence A
A = list(map(int, input().split()))

# Process each query
for _ in range(Q):
# Read the query
i_k, x_k = map(int, input().split())
# Update the sequence A
A[i_k - 1] = x_k
# Print the mex of A
print(mex(A))
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
doubao ```python
N, Q = map(int, input().split())
A = list(map(int, input().split()))

for _ in range(Q):
i, x = map(int, input().split())
A[i - 1] = x
mex = 0
while mex in A:
mex += 1
print(mex)
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE

import sys
import threading
import heapq

def main():
import sys

sys.setrecursionlimit(1 << 25)

N, Q = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
counts = [0]*(N+2) # counts[0..N+1]
missing_numbers = []
for x in A:
if x <= N:
counts[x] +=1
# Build the missing_numbers heap with counts[x]==0
missing_numbers = []
for x in range(N+2):
if counts[x]==0:
heapq.heappush(missing_numbers, x)
for _ in range(Q):
while True:
s = sys.stdin.readline()
if s.strip() != '':
break
i_k_str, x_k_str = s.strip().split()
i_k = int(i_k_str) -1
x_k = int(x_k_str)
old_x = A[i_k]
A[i_k] = x_k
if old_x <= N:
counts[old_x] -=1
if counts[old_x]==0:
heapq.heappush(missing_numbers, old_x)
if x_k <= N:
if counts[x_k]==0:
# We don't remove x_k from missing_numbers heap yet
pass
counts[x_k] +=1

# Output mex
while True:
x = missing_numbers[0]
if counts[x]==0:
print(x)
break
else:
heapq.heappop(missing_numbers)

threading.Thread(target=main).start()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
kimi ```python
from collections import Counter
import sys
input = sys.stdin.readline

def mex(A):
count = Counter(A)
for i in range(max(A) + 2):
if count.get(i, 0) == 0:
return i

def main():
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
count = Counter(A)
mex_val = mex(A)
for _ in range(Q):
(i, x) = map(int, input().split())
i -= 1
if A[i] != x:
count[A[i]] -= 1
if count[A[i]] == 0:
mex_val = min(mex_val, A[i])
count[x] += 1
A[i] = x
print(mex_val)
if count[mex_val] > 0:
mex_val += 1
while count.get(mex_val, 0) > 0:
mex_val += 1

if __name__ == "__main__":
main()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
from sortedcontainers import SortedList

def find_mex(s):
# Find the smallest non-negative integer not in the set
for i in range(s[0] + 1):
if i not in s:
return i
return s[-1] + 1

N, Q = map(int, input().split())
A = list(map(int, input().split()))
s = SortedList(A)

for _ in range(Q):
i, x = map(int, input().split())
s.remove(A[i - 1])
A[i - 1] = x
s.add(x)
print(find_mex(s))
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
wenxinyiyan ```python
# Read the input values
N, Q = map(int, input().split())
A = list(map(int, input().split()))

# Initialize a set to keep track of elements in A and a variable for mex
elements = set(A)
mex = 0

# Process each query
for _ in range(Q):
i, x = map(int, input().split())

# Update the set and sequence A
if A[i-1] in elements:
elements.remove(A[i-1])
A[i-1] = x
elements.add(x)

# Find the mex
while mex in elements:
mex += 1

# Print the mex and reset it for the next query
print(mex)
mex = 0
```
**Note**: The provided code reads the input from `stdin` and writes the output to `stdout` as required. However, it's important to note that for large inputs (as specified in the constraints), using a set to store all elements of `A` and checking for the `mex` in a while loop may not be the most efficient approach. Depending on the specific requirements and constraints of the environment where this code is executed, further optimizations may be necessary.

A more efficient approach could involve using additional data structures, such as a segment tree or a binary indexed tree (BIT), to quickly update and query the minimum missing value. However, implementing such data structures is beyond the scope of this initial response and would require a more detailed understanding of the problem context and performance requirements.		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
zhipu ```python
import sys
input = sys.stdin.read
from collections import defaultdict

def main():
data = input().split()
index = 0

N = int(data[index])
index += 1
Q = int(data[index])
index += 1

A = list(map(int, data[index:index+N]))
index += N

queries = []
for _ in range(Q):
i = int(data[index]) - 1
index += 1
x = int(data[index])
index += 1
queries.append((i, x))

# Frequency dictionary to keep track of counts of each element
freq = defaultdict(int)
for num in A:
freq[num] += 1

# Function to find the current mex
def find_mex():
mex = 0
while freq[mex] > 0:
mex += 1
return mex

results = []
for i, x in queries:
# Decrease the frequency of the old value
old_value = A[i]
freq[old_value] -= 1

# Update the array
A[i] = x

# Increase the frequency of the new value
freq[x] += 1

# Calculate the new mex
results.append(find_mex())

# Output all results
sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == "__main__":
main()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]
deepseek-v3 ```python
# YOUR CODE HERE
import sys
import bisect

def main():
input = sys.stdin.read().split()
ptr = 0
N = int(input[ptr])
Q = int(input[ptr+1])
ptr += 2
A = list(map(int, input[ptr:ptr+N]))
ptr += N

# Initialize frequency map
freq = {}
for num in A:
if num in freq:
freq[num] += 1
else:
freq[num] = 1

# Initialize the mex
mex = 0
while mex in freq:
mex += 1

for _ in range(Q):
i = int(input[ptr]) - 1
x = int(input[ptr+1])
ptr += 2

# Update frequency map
old_val = A[i]
freq[old_val] -= 1
if freq[old_val] == 0:
del freq[old_val]

A[i] = x
if x in freq:
freq[x] += 1
else:
freq[x] = 1

# Recalculate mex
while mex in freq:
mex += 1

# If the old value was less than mex and is now missing, update mex
if old_val < mex and old_val not in freq:
mex = min(mex, old_val)

print(mex)

if __name__ == "__main__":
main()
```		 [{"input": "8 5\n2 0 2 2 1 1 2 5\n4 3\n4 4\n6 3\n8 1000000000\n2 1\n", "output": "4\n3\n6\n5\n0\n", "testtype": "stdin"}]