Do hạn hán, cỏ trên đồng của Nông dân John đã khô héo. Sau nhiều giờ tuyệt vọng và suy ngẫm, Nông dân John nảy ra ý tưởng tuyệt vời là mua ngô để cho những chú bò quý giá của mình ăn.

\(N\) chú bò của FJ (\(1\le N\le 10^5\)) xếp thành một hàng, trong đó chú bò thứ \(i\) có mức đói \(h_i\) (\(0\le h_i\le 10^9\)). Vì bò là động vật có tính xã hội và nhất quyết ăn cùng nhau, cách duy nhất để FJ giảm mức đói của đàn bò là chọn hai chú bò kề nhau \(i\) và \(i+1\), rồi cho mỗi con một túi ngô, khiến mức đói của mỗi con giảm đi một.

FJ muốn cho bò ăn đến khi tất cả có cùng một mức đói không âm. Hãy giúp FJ xác định số túi ngô ít nhất cần dùng để đạt được điều này, hoặc in \(-1\) nếu không thể.

Dữ liệu vào

Mỗi dữ liệu vào gồm nhiều bộ test độc lập, và cần giải đúng tất cả để giải đúng toàn bộ dữ liệu vào. Dòng đầu chứa \(T\) (\(1\le T\le 100\)), là số bộ test cần giải. Tiếp theo là \(T\) bộ test, mỗi bộ được mô tả bằng một cặp dòng. Dòng đầu của mỗi cặp chứa \(N\), dòng thứ hai chứa \(h_1,h_2,\ldots,h_N\). Tổng \(N\) trên mọi bộ test không vượt quá \(10^5\). Giá trị \(N\) có thể khác nhau giữa các bộ test.

Dữ liệu ra

In \(T\) dòng, mỗi dòng ứng với một bộ test.

Lưu ý rằng các số nguyên lớn trong bài có thể đòi hỏi kiểu số nguyên 64 bit (ví dụ long long trong C/C++).

Phân nhóm

• Mọi bộ test trong input 2 thỏa mãn \(N\le 3\) và \(h_i\le 100\).
• Mọi bộ test trong các input 3–8 thỏa mãn \(N\le 100\) và \(h_i\le 100\).
• Mọi bộ test trong các input 9–14 thỏa mãn \(N\le 100\).
• Input 15 không có ràng buộc bổ sung.

Ngoài ra, \(N\) luôn chẵn trong các input 3–5 và 9–11, và \(N\) luôn lẻ trong các input 6–8 và 12–14.

Ví dụ

5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

14
16
-1
-1
-1

Nguồn

USACO 2022 January Contest, Bronze — Drought: https://usaco.org/index.php?page=viewproblem2&cpid=1181

Tác giả: Arpan Banerjee.