First, let’s consider whether there is a winning strategy for Alice when \(k\) is fixed.

It is sufficient to calculate the grundy number. Here, when there is only one pile, the grundy number can be seen to be \(A_i \mod (k+1)\). The proof is by induction.

Therefore, this problem can be rephrased as finding the maximum \(k\) such that the total XOR of \(A_i \mod (k+1)\) is non-zero.

First, if the total XOR of \(A_i\) is non-zero, then for any \(k\) greater than or equal to \(\max(A_i)\), the condition is always satisfied. This means there is no maximum value for \(k\), so the answer is \(-1\).

Let’s consider the other cases. To satisfy the condition, \(k\) must be less than \(\max(A_i)\), so either there is a maximum value for \(k\), or there is no \(k\) that satisfies the condition at all.

Next, for each value \(v\), let \(C_v\) denote the number of \(i\) such that \(A_i=v\). If all \(C_v\) are even, then no matter what value is chosen for \(k\), the total XOR of \(A_i \mod (k+1)\) will always be \(0\). Therefore, we print \(0\) as the answer in such a case.

Let’s consider the other cases. Let \(M\) be the maximum value of \(v\) for which \(C_v\) is odd. If \(k \geq M\), the condition is not satisfied. Next, consider the total XOR of \(A_i \mod (k+1)\) when \(k=M-1\). If we consider the difference from the case \(k=M\), the values that were \(M\) become \(0\), so the total XOR of \(A_i \mod (k+1)\) becomes \(M\). This is notably not \(0\). Therefore, the maximum value of \(k\) that satisfies the condition is \(M-1\).

By implementing the above decision algorithm naively, this problem can be solved in \(O(N \log N)\) time.

Sample Solution