Có ~N~ chiếc hộp trên 1 đường thẳng. Chiếc hộp thứ i có ~A_i~ viên sỏi.
Bạn cần phải di chuyển các viên sỏi giữa các hộp, sao cho lượng sỏi ở các hộp bằng nhau.
Việc di chuyển sỏi được diễn ra trong nhiều lượt, ở mỗi lượt, bạn có thể di chuyển các viên sỏi giữa các hộp kề nhau, theo như mô tả dưới đây:
Hộp ~i~ và hộp ~i+1~ được gọi là kề nhau. Như vậy, các hộp từ 2 đến ~N-1~ có đúng 2 hộp kề nó. Hộp 1 và hộp ~N~ chỉ kề với 1 hộp
Ở mỗi lượt, với mỗi hộp ~i~, bạn được chuyển nhiều nhất 1 viên sỏi sang mỗi hộp kề nó (với hộp ~i~, bạn có thể chuyển tối đa 2 viên sỏi sang 2 hộp kề nó, 1 viên sang hộp ~i-1~ và 1 viên sang hộp ~i+1~).
Việc chuyển đá ở mỗi lượt diễn ra đồng thời. Nghĩa là, bạn không thể chuyển viên đá từ hộp 1 sang hộp 2, rồi trong cùng lượt đó chuyển viên đá từ hộp 2 sang hộp 3.
Nhiệm vụ của bạn là tìm số lượt chuyển ít nhất.
Input
Gồm nhiều bộ test, kết thúc bởi số -1.
Mỗi bộ test gồm:
Dòng 1: ~N~
Một số dòng tiếp theo: ~N~ số nguyên dương, số thứ ~i~ là số viên sỏi trong hộp thứ ~i~.
Output
Nếu không thể chuyển sao cho các hộp có số viên sỏi bằng nhau, in ra -1, ngược lại, in ra số lượt ít nhất.
Sample Input
3
0 99 3
2
49 50
8
16 17 15 0 20 1 1 2
10
0 0 100 0 0 0 0 0 0 0
4
4 0 0 0
-1
Sample Output
34
-1
23
70
3
Note
Ngoài test ví dụ, bài gồm 2 test.
- Test 1: ~N < 25~
- Test 2: ~N < 10,000~
~Ai \le 10^9~
Bình luận