Problem F
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 nonnegative 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

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

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

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

(40 points): $1 \le T \le 4$, $1 \le N \le 100\, 000$
Sample Input 1  Sample Output 1 

2 6 1 3 6 2 7 8 7 1 3 6 2 7 8 5 
15 20 