\(A\) の総和を \(S\) とおきます． 勝利条件は，\(2L-S \leq (\) Alice が消した数の総和\() - (\) Bob が消した数の総和 \() \leq 2R-S\) と言い換えられます． ここで，\(X=S-(L+R)\) とおくことで，条件は更に， \(|X+(\) Alice が消した数の総和\() - (\) Bob が消した数の総和 \()| \leq R-L\) と言い換えられます．

結局，次のような問題が解ければよいです．

• 整数 \(X\) が与えられる．二人が交互に手番をプレイし，Alice は \(X:=X+A_i\)，Bob は \(X:=X-A_i\) という操作を行う（\(i\) は今までに選ばれていない index）．ゲームのスコアを，\(N\) ターン後の \(X\) の絶対値とする．Alice の目的はスコアの最小化であり，Bob の目的はスコアの最大化である．両者が最適に行動した場合，スコアはいくつになるか？

以下，この問題を解く方法を解説します．

\(A\) は昇順にソートされているものとします．

この時，最終的なゲームのスコアは，以下のように求められます．

• 好きな \(p\) を取り，\(p,p+X,A_1,A_2,\cdots,A_N\) をまとめてソートし，\(a_1 \leq a_2 \leq \cdots \leq a_{N+2}\) とする． そして，\((a_2-a_1)+(a_4-a_3)+\cdots+(a_{N+2}-a_{N+1})\) を計算する．
• \(p\) を動かしたときに，上の値としてありうる最小値がゲームのスコアである．

これを実際に計算するのは簡単です．以下は上で求めたスコアが正しいことを証明します．

まず，Alice が \(1\) 手操作し，Bob に手番が回ってきた際のスコアの計算方法を以下に示します．

• 現在の \(X\)，およびまだ選択されていない \(N-1\) 個の数をすべてまとめてソートし，\(b_1 \leq b_2 \leq \cdots \leq b_N\) とする．
• スコアは \((b_2-b_1)+(b_4-b_3)+\cdots+(b_N-b_{N-1})\) になる．

Alice, Bob のスコア計算が正しいことを，まとめて帰納法で示します． \(N=2\) の時の Bob 側のスコア計算が正しいのは明らかです．

\(N=k\) の時の Bob 側のスコア計算が正しいとき，\(N=k\) の時の Alice 側のスコア計算が正しいことを示します． Alice は，いずれかの \(A_i\) を \(A_i+X\) で置き換えた後，Bob 側のスコアを計算した結果を最小化する，という問題を解けばよいです． \(A_i\) を選ぶことは，\(p=A_i\) を選ぶことに対応しています．また，このような形の解で最小値を達成できるので，Alice のゲームのスコアが正しく求められることになります．

\(N=k\) の時の Alice 側のスコア計算が正しいとき，\(N=k+2\) の時の Bob 側のスコア計算が正しいことを示します． Bob が次に選択できる \(N-1\) 個の数と現在の \(X\) をまとめてソートし，\(b_1 \leq b_2 \leq \cdots \leq b_{N}\) とします．\(x\) を \(b_x=X\) となるようにとります．Bob が手番で \(b_y\) \((y \neq x)\) を選んだとき，Alice 側は続けて \(p=b_y\) とすることで，スコアを \((b_2-b_1)+(b_4-b_3)+\cdots+(b_{N}-b_{N-1})\) にすることができます．よってこのスコアが上界であるとわかります．次にこの上界が達成できることを示します． \(x\) が奇数であるとします． \(x=1\) の時は \(y=N\) とし，それ以外の時は \(y=x-1\) とすれば，Alice 側のスコア計算の結果が \((b_2-b_1)+(b_4-b_3)+\cdots+(b_{N}-b_{N-1})\) になります． \(x\) が偶数の場合も同様で，\(x=N\) ならば \(y=1\)，それ以外の時は \(y=x+1\) とすればよいです．

これで帰納法による証明が完了しました．