Xô Sữa

Bessie thách Farmer John với trò chơi gồm $N$ xô sữa xếp hàng, xô thứ $i$ chứa $a_i$ gallon sữa.

Pha 1: Hoán đổi hai xô liền kề (mỗi lần hoán đổi tốn 1 đồng), thực hiện bao nhiêu lần tùy ý.

Pha 2: Lặp lại: chọn hai xô liền kề với lượng sữa $a_i$ và $a_{i+1}$, thay cả hai bằng một xô chứa $\frac{a_i+a_{i+1}}{2}$ gallon, cho đến khi còn 1 xô.

Mục tiêu: tối thiểu hóa số đồng trong Pha 1 để tối đa hóa lượng sữa cuối cùng.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số test case
• Mỗi test case:
  • Dòng 1: Số nguyên $N$
  • Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$

Dữ liệu ra

Với mỗi test case, in ra số đồng tối thiểu cần chi.

Ràng buộc

• $1\le T\le 100$
• $2\le N\le 2\times {10}^5$
• $0\le a_i\le {10}^9$
• Tổng $N$ qua tất cả test case $\le 5\times {10}^5$

Ví dụ