Bessie đã thách đấu Farmer John trong một trò chơi với những xô sữa! Có \(N\) \((2\leq N\leq 2\cdot 10^5)\) xô sữa xếp thành một hàng. Xô thứ \(i\) tính từ bên trái ban đầu chứa \(a_i\) \((0\leq a_i\leq 10^9)\) gallon sữa.

Trò chơi gồm hai giai đoạn:

Giai đoạn 1: Farmer John có thể đổi chỗ hai xô kề nhau bất kỳ. Ông có thể thực hiện bao nhiêu lần đổi chỗ tùy thích, nhưng mỗi lần tốn \(1\) đồng xu.

Giai đoạn 2: Sau khi đổi chỗ, Farmer John thực hiện thao tác sau cho đến khi chỉ còn lại một xô: Chọn hai xô kề nhau có lượng sữa là \(a_i\) và \(a_{i+1}\), rồi thay cả hai xô bằng một xô đặt tại vị trí của chúng và chứa \(\frac{a_i+a_{i+1}}2\) gallon sữa.

Hãy xác định số đồng xu ít nhất Farmer John phải dùng trong giai đoạn đổi chỗ để tối đa hóa lượng sữa trong xô cuối cùng sau khi hoàn tất mọi phép gộp.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(T\) \((1\leq T\leq 100)\): số lượng bộ test độc lập.

Sau đó, với mỗi bộ test, dòng đầu tiên chứa một số nguyên \(N\): số lượng xô sữa. Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\), cách nhau bởi dấu cách: số gallon sữa trong mỗi xô.

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in ra số đồng xu ít nhất Farmer John phải dùng để tối đa hóa lượng sữa trong xô cuối cùng.

Ví dụ

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

Phân nhóm

• Dữ liệu vào 3–4: \(a_i\leq 1\) và \(N\leq 2000\) (tổng \(N\leq 5000\)).
• Dữ liệu vào 5–6: \(a_i\leq 1\).
• Dữ liệu vào 7–9: \(N\leq 2000\) (tổng \(N\leq 5000\)).
• Dữ liệu vào 10–14: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Gold Division — “Milk Buckets”. Tác giả đề: Charlie Yang. https://usaco.org/index.php?page=viewproblem2&cpid=1546