Cỏ trên đồng của bác nông dân John đã bị khô héo do hạn hán. Sau thời gian tuyệt vọng và suy ngẫm, bác John nảy ra một ý tưởng tuyệt vời là mua ngô để nuôi những con bò yêu quí của mình.
Bác John có ~N~ con bò ~(1 \le N \le 10^5)~ được xếp thành ~1~ hàng sao con bò thứ ~i~ của hàng có mức đói là ~h_i~ ~(0 \le h_i \le 10^9)~. Vì bò là động vật xã hội và đòi ăn cùng nhau, nên cách suy nhất để bác John giảm mức đói cho đàn bò của mình là chọn hai con bò kế tiếp nhau lần lượt là con bò thứ ~i~ và thứ ~i + 1~ và cho mỗi con ăn một bao ngô, khi đó mức đói của mỗi con giảm đi ~1~.
Bác John muốn cho những con bò ăn cho đến khi tất cả con bò có cùng mức đói và mức đói là số nguyên không âm. Hãy giúp bác John xác định số lượng bao ngô tối thiểu mà bác cần cho đàn bò ăn, in ra ~-1~ nếu không có cách giải quyết.
Dữ liệu vào
Đảm bảo rằng tổng của các số nguyên ~N~ trong tất cả các test case đều không quá ~10^5~.
Dữ liệu ra
In ra ~T~ dòng, mỗi dòng tương ứng với một test case.
Lưu ý: Vì số nguyên trong bài có thể có kích thước lớn nên yêu cầu dùng kiểu dữ liệu số nguyên ~64-~bit (ví dụ: long long
trong C/C++).
Sample Input
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9
Sample Output
14
16
-1
-1
-1
Giải thích
Scoring
Ngoài ra, ~N~ luôn chẵn ở bộ test ~3-5~ và bộ test ~9-11~, ~N~ luôn lẻ ở bộ test ~6-8~ và bộ test ~12-14~.
Nguồn bài: Arpan Banerjee
Comments