まず \(k\) が固定された場合に Alice に必勝法が存在するかどうか考えます．

grundy 数を計算できれば十分です． ここで，山が \(1\) つのときの grundy 数は，\(A_i \mod (k+1)\) とわかります．証明は帰納法です．

よってこの問題は，\(A_i \mod (k+1)\) の総 XOR が非ゼロになるような最大の \(k\) を求めよ，という風に言い換えられます．

まず，\(A_i\) の総 XOR が非ゼロであった場合，\(k\) が \(\max(A_i)\) 以上であれば常に条件を満たしてしまいます． つまり \(k\) に最大値が存在しないため，\(-1\) が答えです．

そうでないケースを考えます． まず，条件を満たすためには \(k\) は \(\max(A_i)\) 未満である必要があるため，\(k\) の最大値が存在するか，そもそも条件を満たす \(k\) が存在しないかのいずれかになります．

次に，各値 \(v\) について，\(A_i=v\) となる \(i\) の個数を \(C_v\) と置くことにします． \(C_v\) がすべて偶数だった場合，\(k\) としてどのような値を選んでも \(A_i \mod (k+1)\) の総 XOR は \(0\) になってしまいます． よってこのような場合は答えとして \(0\) を出力します．

そうでない場合を考えます． \(C_v\) が奇数となる \(v\) の最大値を \(M\) と置きます． \(k \geq M\) の場合，条件を満たしません． 次に \(k=M-1\) の場合の \(A_i \mod (k+1)\) の総 XOR を考えます． \(k=M\) の場合との差分を考えると，\(M\) だった値が \(0\) に変わるので，\(A_i \mod (k+1)\) の総 XOR は \(M\) になります．これは特に \(0\) ではありません． よって条件を満たす \(k\) の最大値は \(M-1\) になります．

上記の判定アルゴリズムを素直に実装すると \(O(N \log N)\) 時間でこの問題は解けます．

解答例