#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Dynamic MEX - Classic Problems | Repovive

CLS60. Dynamic MEX

2s256 MB

Given an array, process point updates. After each update, print the minimum non-negative integer that is missing from the array.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$0 \le a_i, x \le 10^9$
$1 \le i \le n$

Input

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ i_1 \quad x_1 \\ i_2 \quad x_2 \\ \vdots \\ i_q \quad x_q \end{array}

Output

\begin{array}{l} mex_1 \\ mex_2 \\ \vdots \\ mex_q \end{array}

Samples

Input

Explanation

The MEX values after the four updates are 4, 0, 1, and 3.

Output

Input

Explanation

After each update, the value 1 is missing from the array, so every printed MEX is 1.

Output

1
1
1

Input

Explanation

After removing the only 0, the MEX is 0; after restoring 0, the MEX is 2.

Output

0
2

$1 \le n, q \le 2 \cdot 10^5$
$0 \le a_i, x \le 10^9$
$1 \le i \le n$

\begin{array}{l} n \quad q \\ a_1 \quad a_2 \quad \ldots \quad a_n \\ i_1 \quad x_1 \\ i_2 \quad x_2 \\ \vdots \\ i_q \quad x_q \end{array}

\begin{array}{l} mex_1 \\ mex_2 \\ \vdots \\ mex_q \end{array}