문제

Bessie has challenged Farmer John to a game involving milk buckets! There are $N$ $(2 \leq N \leq 2 \cdot 10^5)$ milk buckets lined up in a row. The $i$-th bucket from the left initially contains $a_i$ $(0 \leq a_i \leq 10^9)$ gallons of milk.

The game consists of two phases:

Phase 1: Farmer John may swap any two adjacent buckets. He may perform as many swaps as he likes, but each swap costs 1 coin.

Phase 2: After swapping, Farmer John performs the following operation until only one bucket is left: Choose two adjacent buckets with milk amounts $a_i$ and $a_{i+1}$, and replace both buckets with one bucket containing $\frac{a_i+a_{i+1}}2$ gallons of milk in their place.

Your goal is to determine the minimum number of coins Farmer John must spend in the swapping phase to maximize the amount of milk in the final bucket after all merges are complete.

입력

The first line contains one integer $T$ $(1 \leq T \leq 100)$: the number of independent test cases.

Then, for each test case, the first line contains an integer $N$: the number of milk buckets. The second line contains $N$ integers $a_1, a_2, \dots, a_N$, separated by spaces: the number of gallons of milk in each bucket.

It is guaranteed that the sum of $N$ over all test cases does not exceed $5 \cdot 10^5.$

출력

For each test case, output the minimum number of coins Farmer John must spend to maximize the amount of milk in the final bucket.

예제 입력 1

2
3
0 0 1
3
0 1 0

예제 출력 1

0
1

예제 입력 2

4
4
9 4 9 2
6
0 0 2 0 0 0
3
2 0 1
9
3 3 3 10 3 2 13 14 13

예제 출력 2

1
2
0
3

점수

Inputs 3-4: $a_i\le 1$ and $N\le 2000$ (sum of $N\le 5000$)Inputs 5-6: $a_i\le 1$Inputs 7-9: $N\le 2000$ (sum of $N\le 5000$)Inputs 10-14: No additional constraints.