A seca secou o pasto de Farmer John. Após horas de desespero e reflexão, tem a brilhante ideia de comprar milho para suas preciosas vacas.

$N$ vacas ($1\le N\le10^5$) em fila, fome $h_i$ ($0\le h_i\le10^9$). São sociais e exigem comer juntas: única forma, dar um saco a cada vizinha $i,i+1$, reduzindo cada fome em um.

Quer fomes iguais e não negativas. Ache mínimo de sacos ou -1 se impossível.

Entrada

Vários casos independentes, todos devem ser resolvidos corretamente. Primeiro $T$ ($1\le T\le100$), depois duas linhas por caso, $N$ e $h_1,h_2,\ldots,h_N$. Soma $N$ no máximo $10^5$, os $N$ podem diferir.

Saída

$T$ linhas, uma por caso.

Valores grandes podem exigir 64 bits, como C/C++ long long.

Exemplos

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

Saída 1

14
16
-1
-1
-1

Note

No primeiro, dois sacos cada para 2,3, depois cinco cada para 1,2: todas fome 3.

No segundo, dois cada para 1,2, para 2,3, para 4,5 e para 5,6: todas fome 2.

Nos demais, impossível igualar.

Subtarefas

• Todos os casos da entrada 2: $N\le3$, $h_i\le100$.
• Todos das entradas 3–8: $N\le100$, $h_i\le100$.
• Todos das entradas 9–14: $N\le100$.
• Entrada 15 sem restrições adicionais.

Além disso $N$ sempre par em 3–5 e 9–11, ímpar em 6–8 e 12–14.

Autor: Arpan Banerjee