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.

\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}

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

\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}