If Snuke can take the largest \(N/2\) in \(A\), it is guaranteed to be the largest score possible.

We claim that it is achievable.

Let us correspond the largest \(N/2\) values in \(A\) to \(-1\) and the other values to \(+1\) to make a sequence \(B\) of length \(N\) consisting of \(-1\) and \(+1\). (Ties can be broken arbitrarily.)

If \(B\) satisfies the following condition, Snuke can take all values corresponding to \(-1\).

• Any prefix sum of \(B\) is zero or greater.

It can be proved as follows. First, Snuke will take the nearest \(-1\) to the beginning. From the prefix sum condition, \(B\) always begins with \(+1\), which will be taken by Mr. Min next. Here, we see that the prefix sum condition on \(B\) is still satisfied. (The only thing that happened in those two turns is a sequence \(+1, -1\) getting removed, which does not affect the prefix sums anywhere else.)

Therefore, the problem is solved if we can cyclically shift \(B\) to satisfy the condition above.

Now, let us define \(C_0=0,C_i=C_{i-1}+B_i\) (\(1 \leq i \leq N\)). We can see that the condition is satisfied by cyclically shifting \(B\) by \(x\) to the left, where \(C_x\) is the minimum value in \(C\).

The complexity of this method is \(O(N \log N)\) in total, the bottleneck being the sorting to find the largest \(N/2\) in \(A\). (We can make it \(O(N)\) by using std::nth_element etc.)

Sample submission (c++)