Susza wysuszyła trawę Farmer John. Po godzinach rozpaczy i rozmyślań wpada na genialny pomysł kupienia kukurydzy ukochanym krowom.

$N$ krów ($1\le N\le10^5$) w szeregu, głód $h_i$ ($0\le h_i\le10^9$). Towarzyskie, chcą jeść razem: jedyna metoda dać sąsiadkom $i,i+1$ po worku, zmniejszając głód każdej o jeden.

Chce głód wszystkich równy i nieujemny. Znajdź minimum worków albo -1, jeśli niemożliwe.

Wejście

Kilka niezależnych testów, wszystkie trzeba rozwiązać poprawnie. Najpierw $T$ ($1\le T\le100$), potem po dwa wiersze: $N$, $h_1,h_2,\ldots,h_N$. Suma $N$ do $10^5$, $N$ może się różnić.

Wyjście

$T$ wierszy, po jednym na test.

Duże wartości mogą wymagać 64 bitów, np. C/C++ long long.

Przykład

Wejście 1

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

Wyjście 1

14
16
-1
-1
-1

Uwagi

W pierwszym 2,3 po dwa worki, potem 1,2 po pięć, głód wszystkich 3.

W drugim 1,2 po dwa, 2,3 po dwa, 4,5 po dwa, 5,6 po dwa, głód wszystkich 2.

W pozostałych niemożliwe wyrównanie.

Podzadania

• Wszystkie testy wejścia 2: $N\le3$, $h_i\le100$.
• Wszystkie testy 3–8: $N\le100$, $h_i\le100$.
• Wszystkie testy 9–14: $N\le100$.
• Wejście 15 bez dalszych ograniczeń.

Ponadto $N$ zawsze parzyste w 3–5 i 9–11, nieparzyste w 6–8 i 12–14.

Autor: Arpan Banerjee