La sécheresse a séché l’herbe de Farmer John. Après des heures de désespoir et de réflexion, il a l’idée brillante d’acheter du maïs pour ses précieuses vaches.

$N$ vaches ($1\le N\le10^5$) sont en ligne, avec faim $h_i$ pour la $i$ ($0\le h_i\le10^9$). Sociales, elles exigent de manger ensemble : seule méthode, donner aux voisines $i,i+1$ un sac chacune, diminuant chacune de un.

Il veut toutes les faims égales et non négatives. Trouvez le minimum de sacs, ou -1 si impossible.

Entrée

Plusieurs tests indépendants, tous à résoudre correctement. D’abord $T$ ($1\le T\le100$), puis deux lignes par test : $N$, puis $h_1,h_2,\ldots,h_N$. Somme des $N$ au plus $10^5$ ; les $N$ peuvent différer.

Sortie

$T$ lignes, une par test.

Les grands nombres peuvent nécessiter 64 bits, comme C/C++ long long.

Exemples

Entrée 1

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

Sortie 1

14
16
-1
-1
-1

Remarque

Au premier, deux sacs chacune pour 2,3 puis cinq chacune pour 1,2 : toutes les faims sont 3.

Au deuxième, deux chacune pour 1,2, puis 2,3, puis 4,5, puis 5,6 : faim 2 partout.

Aux autres, impossible d’égaliser.

Sous-tâches

• Tous les tests de l’entrée 2 : $N\le3$, $h_i\le100$.
• Tous ceux des entrées 3–8 : $N\le100$, $h_i\le100$.
• Tous ceux des entrées 9–14 : $N\le100$.
• Entrée 15 sans contrainte supplémentaire.

De plus, $N$ toujours pair dans 3–5 et 9–11, toujours impair dans 6–8 et 12–14.

Auteur : Arpan Banerjee