Problem Description

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.

Input Format

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$.

Output Format

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

2
3
0 0 1
3
0 1 0

0
1

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

1
2
0
3

Hint

For the first test, we do not need to swap any milk buckets in the first phase. In the second phase, Farmer John can merge the first two buckets and then merge the only two buckets left to achieve a final amount of $0.5$. It can be shown that this final amount is maximal.

For the second test, we must perform a singular swap of the first two milk buckets in the first stage to achieve a final amount of $0.5$ in the second stage. It can be shown that we cannot achieve a final amount of $0.5$ without swaps in the first stage.

For the first test, Farmer John can swap the second and the third buckets in the first phase. Then, in the second phase, Farmer John can perform the following:

• $[9,9,4,2]$ -> merge the third and fourth buckets ->
• $[9,9,3]$ -> merge the second and third buckets ->
• $[9,6]$ -> merge the first and second buckets ->
• $[7.5]$

The final amount of milk is $7.5$, which is the maximum possible. It can be shown that even with additional swaps, the final amount cannot exceed $7.5$, and that with fewer swaps, the final amount cannot reach $7.5$.

• 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.