La siccità ha seccato l’erba di Farmer John. Dopo ore di disperazione e riflessione, ha la brillante idea di comprare mais per le amate mucche.

$N$ mucche ($1\le N\le10^5$) in fila, fame $h_i$ ($0\le h_i\le10^9$). Sociali, vogliono mangiare insieme: unico modo, dare un sacco ciascuna alle vicine $i,i+1$, diminuendo ciascuna fame di uno.

Vuole fame uguale e non negativa per tutte. Trova minimo di sacchi, o -1 se impossibile.

Input

Più casi indipendenti devono essere tutti risolti correttamente. Prima $T$ ($1\le T\le100$), poi due righe per caso: $N$ e $h_1,h_2,\ldots,h_N$. Somma $N$ al massimo $10^5$, $N$ può differire.

Output

$T$ righe, una per caso.

Valori grandi possono richiedere 64 bit, come C/C++ long long.

Esempi

Input 1

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

Output 1

14
16
-1
-1
-1

Note

Nel primo due sacchi ciascuna per 2,3, poi cinque ciascuna per 1,2: fame 3 per tutte.

Nel secondo due ciascuna per 1,2, per 2,3, per 4,5 e per 5,6: fame 2 per tutte.

Negli altri impossibile uguagliare.

Sottoproblemi

• Tutti i casi dell’input 2: $N\le3$, $h_i\le100$.
• Tutti di 3–8: $N\le100$, $h_i\le100$.
• Tutti di 9–14: $N\le100$.
• Input 15 senza altri vincoli.

Inoltre $N$ sempre pari in 3–5 e 9–11, dispari in 6–8 e 12–14.

Autore: Arpan Banerjee