Let \(S\) be the sum of \(A\). The win condition can be rephrased into \(2L-S \leq (\) sum of numbers Alice erases \() - (\) sum of numbers Bob erases \() \leq 2R-S\) By letting \(X=S-(L+R)\), it can be further rephrased into \(|X+(\) sum of numbers Alice erases \() - (\) sum of numbers Bob erases \()| \leq R-L\).

Eventually, we want to solve the following problem.

• Given is an integer \(X\). The two players take alternating turns, where Alice does the operation \(X:=X+A_i\) and Bob does the operation \(X:=X-A_i\) (\(i\) is an index that is not yet chosen). Let the score of the game be the absolute value of \(X\) after \(N\) turns. Alice’s objective is to minimize the score, while Bob’s is to maximize it. What will be the score if both players play optimally?

We will explain the solution to this problem.

Assume \(A\) is sorted in ascending order.

Then, the final score can be found as follows.

• Choose any \(p\) and sort the values \(p,p+X,A_1,A_2,\cdots,A_N\) to have \(a_1 \leq a_2 \leq \cdots \leq a_{N+2}\). Then, compute \((a_2-a_1)+(a_4-a_3)+\cdots+(a_{N+2}-a_{N+1})\).
• The score of the game will be the minimum possible value of the above when \(p\) can be chosen freely.

Computing this value itself is easy. Below, we will prove that the score found above is correct.

First, here is the way to compute the score when Alice plays one turn and Bob takes his turn.

• Sort the \(N-1\) numbers not yet chosen together along with the current \(X\), to have \(b_1 \leq b_2 \leq \cdots \leq b_N\).
• The score will be \((b_2-b_1)+(b_4-b_3)+\cdots+(b_N-b_{N-1})\).

We will prove that the above computations of scores for Alice and Bob are correct, both at once, by induction. It is obvious that the computation for Bob when \(N=2\) is correct.

We prove that when the computation for Bob when \(N=k\) is correct, the computation for Alice when \(N=k\) is correct. Alice’s objective is to solve the problem of replacing one of the \(A_i\)’s with \(A_i+X\) to minimize the result of the computation for Bob. Choosing \(A_i\) corresponds to choosing \(p=A_i\), and this form of a solution can achieve the minimum value, which means that the score for Alice is computed correctly.

We prove that when the computation for Alice when \(N=k\) is correct, the computation for Bob when \(N=k+2\) is correct. Let us sort the \(N-1\) numbers that Bob can choose next along with the current \(X\), to have \(b_1 \leq b_2 \leq \cdots \leq b_N\). Take \(x\) such that \(b_x=X\). If Bob chooses \(b_y\) \((y \neq x)\) in his turn, Alice can then let \(p=b_y\) to make the score \((b_2-b_1)+(b_4-b_3)+\cdots+(b_{N}-b_{N-1})\), so we see that this value is the upper bound of the score. Next, we show that this upper bound can be achieved. Assume \(x\) is odd. If Bob chooses \(y=N\) if \(x=1\) and \(y=x-1\) otherwise, the result of the computation for Alice will be \((b_2-b_1)+(b_4-b_3)+\cdots+(b_{N}-b_{N-1})\). The case with even \(x\) is similar: Bob should choose \(y=1\) if \(x=N\) and \(y=x+1\) otherwise.

This completes the proof by induction.