La sequía secó el pasto de Farmer John. Tras horas de desesperación y reflexión, tiene la brillante idea de comprar maíz para sus queridas vacas.

$N$ vacas ($1\le N\le10^5$) en fila, hambre $h_i$ ($0\le h_i\le10^9$). Son sociales y comen juntas: única forma, elegir vecinas $i,i+1$, dar un saco a cada una, reduciendo cada hambre en uno.

Quiere hambres iguales no negativas. Halla mínimo de sacos, o -1 si imposible.

Entrada

Varios casos independientes, todos deben resolverse bien. Primero $T$ ($1\le T\le100$), luego dos líneas por caso, $N$ y $h_1,h_2,\ldots,h_N$. Suma $N$ hasta $10^5$, los $N$ pueden variar.

Salida

$T$ líneas, una por caso.

Valores grandes pueden necesitar 64 bits, como C/C++ long long.

Ejemplos

Entrada 1

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

Salida 1

14
16
-1
-1
-1

Nota

En primero, dos sacos cada una para 2,3, luego cinco cada una para 1,2: todas hambre 3.

En segundo, dos cada una para 1,2, para 2,3, para 4,5, para 5,6: todas hambre 2.

En los restantes, imposible igualar.

Subtareas

• Todos los casos de entrada 2: $N\le3$, $h_i\le100$.
• Todos de entradas 3–8: $N\le100$, $h_i\le100$.
• Todos de entradas 9–14: $N\le100$.
• Entrada 15 sin restricciones adicionales.

Además $N$ siempre par en 3–5 y 9–11, siempre impar en 6–8 y 12–14.

Autor: Arpan Banerjee