First, assume that \(A_{N-1}+2 \leq A_N\). It turns out that the first player always wins in this case, from the following argument.

• If the first player can make \(A_N\) less than \(A_{N-1}\) and foist a losing board on the second player, the first player wins.
• Assume that all boards that can be obtained by making \(A_N\) less than \(A_{N-1}\) are winning. Then, if we change \(A_N\) to \(A_{N-1}+1\), all boards that can be transitioned from that board are winning. Thus, the board obtained by changing \(A_N\) to \(A_{N-1}+1\) is losing. Therefore, the initial board is winning.

Next, consider when a board with \(A_N=A_{N-1}+1\) is given. It can be seen from the above argument that a player should never give a board where the two largest elements have the difference of \(2\) or greater. Thus, throughout the game, we can assume that the two largest elements of \(A\) have the difference of \(1\).

Then, we can see that each operation decreases \(\max(A)\) by \(1\), regardless of how it is done.

A board with \(\max(A)=N-1\) is unplayable, so the winner can be determined from the difference between the parities of \(A_N\) and \(N-1\) in input.

The complexity of the solution is \(O(N)\).

Sample Submission (C++)