Dürre hat Farmer Johns Gras vertrocknet. Nach Stunden der Verzweiflung und Überlegung hat er die brillante Idee, Mais für seine geliebten Kühe zu kaufen.

$N$ Kühe ($1\le N\le10^5$) stehen in Reihe, Hunger $h_i$ ($0\le h_i\le10^9$). Sozial wie sie sind, wollen sie zusammen essen: einzige Methode, Nachbarn $i,i+1$ je einen Sack geben, Hunger jeweils um eins senken.

Alle sollen gleichen nichtnegativen Hunger haben. Finde minimale Sackzahl oder -1, falls unmöglich.

Eingabe

Mehrere unabhängige Tests müssen alle korrekt gelöst werden. Zuerst $T$ ($1\le T\le100$), dann je zwei Zeilen: $N$ und $h_1,h_2,\ldots,h_N$. Summe $N$ höchstens $10^5$, $N$ darf variieren.

Ausgabe

$T$ Zeilen, je eine pro Test.

Große Werte können 64-Bit-Typen brauchen, etwa C/C++ long long.

Beispiele

Eingabe 1

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

Ausgabe 1

14
16
-1
-1
-1

Hinweis

Zuerst 2,3 je zwei Säcke, dann 1,2 je fünf: Hunger aller 3.

Im zweiten 1,2 je zwei, 2,3 je zwei, 4,5 je zwei, 5,6 je zwei: Hunger aller 2.

In den übrigen unmöglich.

Teilaufgaben

• Alle Tests in Eingabe 2: $N\le3$, $h_i\le100$.
• Alle in 3–8: $N\le100$, $h_i\le100$.
• Alle in 9–14: $N\le100$.
• Eingabe 15 ohne weitere Einschränkungen.

Zusätzlich $N$ immer gerade in 3–5 und 9–11, ungerade in 6–8 und 12–14.

Aufgabenautor: Arpan Banerjee