Median Game
/

## Algorithms, June Easy 19, Logic-Based, Merge sort, Sorting

Problem
Editorial
Analytics

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.

SAMPLE INPUT
2
4
2 5 3 2
4
1 1 1 1

SAMPLE OUTPUT
7
2

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

## This Problem was Asked in

Initializing Code Editor...