Problem C
Continuous Median

In Statistics, the median of an array $\textbf{A}$ of $\textbf{N}$ integers is a value which divides array $\textbf{A}$ into two equal parts: the higher half and the lower half.

In the case when $\textbf{N}$ is odd, the median is clearly defined: the middle value of the sorted version of array $\textbf{A}$. In the case when $\textbf{N}$ is even, the median is the average of the two middle values, rounded down so that we always have an integer median.

In this problem, your task is to compute median values as integers are added into array $\textbf{A}$ one by one. Since this is an incremental process, we call these “continuous medians”. To simplify this problem, you just need to output the sum of the medians of $\textbf{A}$ at the end.

Input

The first line of input contains an integer $T$, denoting the number of test cases $(1 \le T \le 100)$. Each test case consists of two lines and the first line contains just one integer $N$ $(1 \le N \le 10^{5})$. This is followed by $N$ integers of array $\textbf{A}$ in the next line. Each integer in $\textbf{A}$ is non-negative and is not more than $10^{9}$.

Note: For all input, there will be at most $400\, 000$ integers.

Output

For each test case, output the sum of the continuous medians of $\textbf{A}$ in one line.

Explanation

In the first sample test case, $N = 6$ and $\textbf{A} = \{ 1, 3, 6, 2, 7, 8\} $. When you read the $i^\textrm {th}$ integer of array $\textbf{A}$, you need to compute the current continuous median of array $\textbf{A} = [A_{0}, A_{1}, \ldots , A_{i}]$, as shown in Table 1. Thus, $1+2+3+2+3+4 = 15$ is the answer for this first sample test case.

Subtasks

1. (10 points): $1 \le T \le 20$, $1 \le N \le 500$

2. (10 points): $1 \le T \le 100$, $1 \le N \le 500$

3. (40 points): $1 \le T \le 100$, $1 \le N \le 3\, 000$

4. (40 points): $1 \le T \le 4$, $1 \le N \le 100\, 000$

2
6
1 3 6 2 7 8
7
1 3 6 2 7 8 5

15
20