No.2126 MEX Game
Problem Statement
You are given a sequence of non-negative integers $A=(A_1,\ldots,A_N)$ of length $N$.
Sente and Gote play a game using this sequence of non-negative integers.
Starting with Sente, the $2$ players alternately perform the following action $1$ time each, for a total of $10^{5000}$ actions by the $2$ players combined:
Sente acts so that the mex of $A$ after all operations by the $2$ players are finished becomes large, and Gote acts so that it becomes small.
Find the value of the mex of $A$ after all operations by the $2$ players are finished, when both players follow optimal strategies to achieve their respective goals.
Here, the mex of $A$ is defined as follows:
Constraints
Input
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Output the value of the mex of $A$ after all operations are finished.
Sample
Sample 1
Input
3 0 1 0
Output
1
By repeating the operation of changing an element of $A$ that is not $0$ to $0$ (or changing $A_1$ to $0$ if no such element exists), Sente can make the final mex of $A$ equal to $1$.
Conversely, Sente cannot make the mex of $A$ $2$ or greater, so output $1$.
Sample 2
Input
1 2022
Output
0
No matter how Sente operates, Gote can make the final mex of $A$ equal to $0$, for example by changing $A_1$ to $2040$.
Sample 3
Input
9 0 0 0 1 1 0 0 1 1
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。