Page not loading? Try clicking here.
Placeholder

#8859
Subtask

Milk Buckets 1s 1024MB

Problems

Bessie has challenged Farmer John to a game involving milk buckets! There are N (2≤N≤2⋅10^5) milk buckets lined up in a row. The i-th bucket from the left initially contains a_i (0≤a_i≤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

The first line contains one integer T (1≤T≤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,…,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⋅10^5.


Output

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


Subtask

# Score Condition
#110

a_i≤1 and N≤2000 (sum of N≤5000)

#220

a_i≤1

#330

N≤2000 (sum of N≤5000)

#440

추가 제약 조건 없음


Example #1

2
3
0 0 1
3
0 1 0
0
1

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.


Example #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
1
2
0
3

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.


Source

USACO 2026 First Contest, Gold

You must sign in to write code.