Hạn hán làm cỏ Farmer John khô. Sau nhiều giờ tuyệt vọng và suy nghĩ, ông nảy ý tuyệt vời mua ngô cho đàn bò quý.

$N$ bò ($1\le N\le10^5$) một hàng, đói $h_i$ ($0\le h_i\le10^9$). Chúng thích xã giao, nhất quyết ăn cùng: cách duy nhất cho hai bò kề $i,i+1$ mỗi con một bao, giảm đói mỗi con một.

Muốn tất cả đói bằng nhau không âm. Tìm số bao tối thiểu, hoặc -1 nếu không thể.

Dữ liệu vào

Nhiều test độc lập, phải giải đúng tất cả. Đầu $T$ ($1\le T\le100$), mỗi test hai dòng: $N$, $h_1,h_2,\ldots,h_N$. Tổng $N$ tối đa $10^5$, mỗi $N$ có thể khác.

Dữ liệu ra

$T$ dòng, mỗi test một dòng.

Số lớn có thể cần 64 bit, như C/C++ long long.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

14
16
-1
-1
-1

Ghi chú

Test đầu cho 2,3 mỗi con hai bao, rồi 1,2 mỗi con năm bao, tất cả đói 3.

Test hai cho 1,2 mỗi con hai, 2,3 mỗi con hai, 4,5 mỗi con hai, 5,6 mỗi con hai, tất cả đói 2.

Các test còn lại không thể bằng nhau.

Nhiệm vụ con

• Tất cả test đầu vào 2: $N\le3$, $h_i\le100$.
• Tất cả test 3–8: $N\le100$, $h_i\le100$.
• Tất cả test 9–14: $N\le100$.
• Đầu vào 15 không thêm ràng buộc.

Ngoài ra $N$ luôn chẵn trong 3–5 và 9–11, lẻ trong 6–8 và 12–14.

Tác giả: Arpan Banerjee