FJ’s NN cows (1≤N≤10**51≤N≤10**5) are arranged in a line such that the iith cow in line has a hunger level of hihi (0≤hi≤10**90≤hi≤109). As cows are social animals and insist on eating together, the only way FJ can decrease the hunger levels of his cows is to select two adjacent cows ii and i+1i+1 and feed each of them a bag of corn, causing each of their hunger levels to decrease by one.

FJ wants to feed his cows until all of them have the same non-negative hunger level. Please help FJ determine the minimum number of bags of corn he needs to feed his cows to make this the case, or print −1−1 if it is impossible.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in 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

For the first test case, give two bags of corn to both cows 22 and 33, then give five bags of corn to both cows 11 and 22, resulting in each cow having a hunger level of 33.

For the second test case, give two bags to both cows 11 and 22, two bags to both cows 22 and 33, two bags to both cows 44 and 55, and two bags to both cows 55 and 66, resulting in each cow having a hunger level of 22.

For the remaining test cases, it is impossible to make the hunger levels of the cows equal.

Problem credits: Arpan Banerjee