You are given an integer array \(a\) of size \(n\). The elements of the array are numbered from \(1\) to \(n\).
You can perform the following operation any number of times (possibly, zero): choose an index \(i\) from \(1\) to \(n\); decrease \(a_i\) by \(2\) and increase \(a_{(i \bmod n) + 1}\) by \(1\).
After you perform the operations, all elements of the array should be non-negative equal integers.
Your task is to calculate the minimum number of operations you have to perform.
Output
For each test case, print a single integer — the minimum number of operations you have to perform. If it is impossible to make all elements of the array equal, print -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 1
3
1 3 2
4
2 1 2 6
|
0
-1
3
|