We split this problem into two cases:

Odd ~N~: We arrange the array in non-decreasing order. For example, let the array be ~a, b, c, d, e~ such that ~a \le b \le c \le d \le e~. It is easy to see that if Ken picks ~e~, it is always optimal for his opponent to pick ~d~, the next largest available number. If his opponent picks ~a~, he leaves the current largest number in the line, ~d~, available to Ken. Ken then picks ~c~, causing his opponent to pick ~b~. Finally, Ken picks ~a~. Since Ken's total after the first ~\frac{N-1}{2}~ moves is always greater or equal to his opponent's, the selection of the ~N^\text{th}~ or smallest element guarantees him the win.

Even ~N~: We first realize the only case where the answer is ~-1~ is when all elements in the array are the same.

We start by sorting the array in non-decreasing order. Let us call the first half of the array (the larger half) ~b~ and the second half (the smaller half) ~c~. We arrange ~a~ in the following manner: ~b_i, c_i, b_j, c_j, \dots, b_z, c_z~.

To understand why, consider that on each of Ken's turns, he picks an element from ~b~. Then, his opponent is always left with an element from ~c~. This process repeats until Ken selects the entire array ~b~ and his opponent selects the entire array ~c~. Since all elements in ~b~ are greater than or equal to all elements in ~c~ and the array consists of more than one distinct number, the sum of elements in ~b~ must be strictly greater than the sum of elements in ~c~, as desired.

Time Complexity: ~\mathcal{O}(T \cdot N \log N)~