まず，\(A_{N-1}+2 \leq A_N\) だとします． 実はこの時は必ず先手必勝です． これは以下の議論からわかります．

• \(A_N\) を \(A_{N-1}\) 未満にして，後手必勝盤面を相手に押し付けられるなら，先手の勝ち．
• \(A_N\) を \(A_{N-1}\) 未満にして得られる盤面がすべて先手必勝盤面だとする．このとき，\(A_N\) を \(A_{N-1}+1\) にすれば，この盤面から遷移できるのはすべて先手必勝盤面．つまり \(A_N\) を \(A_{N-1}+1\) にして得られる盤面は後手必勝．よって最初の盤面は先手必勝．

次に，\(A_N=A_{N-1}+1\) の盤面が渡された場合を考えます． 以上の議論より，最も大きい \(2\) つの要素の差が \(2\) 以上の盤面を相手に渡してはいけないとわかります． よって，ゲームを通じて \(A\) の状態は，最も大きいの \(2\) つの要素の差が \(1\) であるとしてよいです．

すると，どのような操作を行うとしても，\(\max(A)\) は一回操作する度に \(1\) 減るとわかります．

\(\max(A)=N-1\) が明らかに操作不能な盤面なので，結局，入力の \(A_N\) と \(N-1\) の偶奇の違いで先手必勝かどうかがわかります．

計算量は \(O(N)\) です．

解答例(c++)