\(A\) の中で大きい方から \(N/2\) 個をすべてすぬけ君が取れば，これは明らかに最大です．

そして，実際にこれは達成可能です．

\(A\) の中で大きい方から \(N/2\) 番目以内にある値を \(-1\)，そうでない値を \(+1\) に対応させて，\(-1,+1\) からなる長さ \(N\) の数列 \(B\) を作ってみます．（\(A\) の中での値のタイブレークは自由に行って良いです．）

もし，\(B\) が次の条件を満たすなら，すぬけ君は \(-1\) に対応する位置の値をすべて取ることができます．

• \(B\) の先頭からの累積和を考えた時，常に \(0\) 以上である．

これは以下のように証明できます． まずすぬけ君は，\(-1\) のうち，最も先頭に近い位置を選んで取ります． 累積和の条件より，\(B\) の先頭は必ず \(+1\) であり，最小太郎くんは次にこれを取ることになります． ここで，\(B\) の累積和の条件が依然として成立していることが確認できます．（\(2\) ターンをまとめて見ると，\(+1,-1\) という並びが抜けただけなので，他の部分の累積和に影響していない．）

よって，\(B\) を適切に cyclic-shift し，上の条件が成り立つようにできればこの問題は解けます．

ここで，\(C_0=0,C_i=C_{i-1}+B_i\) (\(1 \leq i \leq N\)) と定義してみます． ここで，\(C\) の最小値を \(C_x\) とすると，\(B\) を左に \(x\) 個 cyclic-shift すれば条件が満たされることがわかります．

計算量は，\(A\) の大きい方から \(N/2\) 個を求めるパートで使うソートがボトルネックになり，全体で \(O(N \log N)\) になります． （std::nth_element などを用いることで \(O(N)\) にすることも可能です．）

解答例(c++)