SOLVE

LATER

Median Game

/

You are given an array \(A\) of \(N\) integers. You perform this operation \(N - 2\) times: For each contiguous subarray of **odd size** greater than \(2\), you find the median of each subarray(Say medians obtained in a move are \(M_1, M_2, M_3,\ldots, M_k\)). In each move, you remove the first occurrence of value \(min(M_1, M_2, M_3,\ldots, M_k)\) from the original array. After removing the element the array size reduces by 1 and no void spaces are left. For example, if we remove element \(2\) from the array \(\{1, 2, 3, 4\}\), the new array will be \(\{1, 3, 4\}\).

Print a single integer denoting the sum of numbers that are left in the array after performing the operations. You need to do this for \(T\) test cases.

**Input Format**

The first line contains \(T\) denoting the number of test cases(\(1 \le T \le 10\)).

The first line of each test case contains \(N\) denoting the number of integers in the array initially(\(4 \le N \le 10^5\)).

The next line contains \(N\) space seperated integers denoting \(A_1, A_2, A_3,\ldots, A_N\)(\(1 \le A_i \le 10^9\) for all valid \(i\)).

**Output Format**

Output a single integer denoting the sum of numbers left in the array after performing the operations for each test case on a new line.

Explanation

For the first test case: Initially, array is \(\{2, 5, 3, 2\}\). The medians obtained are \(\{3, 3\}\) for subarrays \([1, 3]\) and \([2, 4]\) respectively. Hence, we remove \(min(3, 3) = 3\) from the initial array. The array now becomes \(\{2, 5, 2\}\). The median of the whole array is \(2\). Hence we remove the first occurrence of \(2\) from the array. So, we are left with \(\{5, 2\}\) in our array.

For the second test case, it is obvious that the minimum medium will be \(1\) every time. Hence finally, we will be left with \(\{1, 1\}\) as the array.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...