Dãy số cân bằng - VNOJ: VNOI Online Judge

Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, ldots, a_n~. Ban dãy ~a~ thỏa mãn điều kiện ~a_1 le 2cdot a_i~ với mọi ~2 le i le n~. Đây được gọi là điều kiện cân bằng của dãy ~a~.

Được phép thực hiện dãy các tác sau không hoặc nhiều lần:

• Chọn chỉ số ~i~ (~2 le i le n~) và số nguyên ~x~ sao cho ~x le a_i~.

• Thực hiện biến đổi ~a_1 gets a_1 + x~ và ~a_i gets a_i - x~.

• Sau phép biến đổi, điều kiện cân bằng của mảng ~a~ phải được thỏa mãn.

• ~x~ được gọi là điểm số cho thao tác này.

Tìm tổng điểm số lớn nhất có thể sau khi thực hiện thao tác trên không hoặc nhiều lần.

Input

Bộ dữ liệu gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 le t le 100~) là số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên ~n~ (~2 le n le 200,000~) — độ dài dãy ~a~.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ldots, a_n~ (~1 le a_i le 10^9~, ~a_1 le 2 a_i~ với mọi ~2 le i le n~).

Dữ liệu đảm bảo rằng tổng ~n~ trong tất cả các test case không quá ~2 cdot 10^5~.

Output

Với mỗi test case, hãy in ra tổng điểm số tối đa có thể đạt được sau khi thực hiện thao tác không hoặc vài lần.

Scoring

Subtask Điểm Ràng buộc 1 ~250~ ~n le 100~, ~a_i le 100~ 2 ~250~ Không có ràng buộc gì thêm Tổng ~500~

Sample Input 1

3 3 2 3 4 2 1 11 4 5 3 3 3

Sample Output 1

2 7 0

Notes

Với testcase thứ nhất, tổng điểm số tối đa có thể đạt được là ~2~:

• ta có ~x = 1~ điểm khi chọn ~i = 2~. Lúc này ta có dãy ~a = [3, 2, 4]~

• ta có ~x = 1~ điểm khi chọn ~i = 3~. Lúc này ta có dãy ~a = [4, 2, 3]~.

Với testcase thứ hai, tổng số điểm ta có thể đạt được là ~7~ bằng cách chuyển ~x = 7~ điểm từ vị trí ~i = 2~. Ta thu được dãy ~a = [8, 4]~.

Ở test case thứ ba, ta không có cách tăng điểm nào để thỏa mãn điều kiện cân bằng của dãy ~a~.