Yuki tiene una sucesión $a$ de longitud $n$.

Yuki define una operación de la siguiente manera:

• Elige un intervalo $[l, r]$ de longitud par. Para cada entero $i$ tal que $l \le i \le r$:
  • Si $i - l$ es impar, el valor de $a_i$ disminuye en $1$, es decir, $a_i \leftarrow a_i - 1$.
  • Si $i - l$ es par, el valor de $a_i$ aumenta en $1$, es decir, $a_i \leftarrow a_i + 1$.

Ahora, Yuki quiere realizar cierto número de operaciones de modo que todos los números en la sucesión $a$ sean iguales. Debes ayudar a Yuki a encontrar el número mínimo de operaciones necesarias para hacer que todos los números en la sucesión $a$ sean iguales, o informar si es imposible.

Entrada

Este problema contiene múltiples casos de prueba.

La primera línea contiene un entero positivo $t$ ($1 \le t \le 10^5$), que representa el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene un entero positivo $n$ ($1 \le n \le 10^6$).
• La segunda línea contiene $n$ enteros $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime una línea:

• Si es imposible, imprime $-1$.
• Si es posible, imprime un entero que represente el número mínimo de operaciones para hacer que todos los números en la sucesión $a$ sean iguales.

Ejemplos

Entrada 1

3
2
1 3
4
1 5 1 5
5
1 3 1 3 1

Salida 1

1
2
-1

Nota

Para el primer caso de prueba:

• Realiza la operación en el intervalo $[1, 2]$. La sucesión se convierte en $2, 2$, donde todos los números son iguales.
• Se puede demostrar que no existe ninguna solución con menos operaciones, por lo que la respuesta es $1$.

Para el segundo caso de prueba:

• Realiza la operación en el intervalo $[1, 4]$. La sucesión se convierte en $2, 4, 2, 4$.
• Realiza la operación en el intervalo $[1, 4]$. La sucesión se convierte en $3, 3, 3, 3$, donde todos los números son iguales.
• Se puede demostrar que no existe ninguna solución con menos operaciones, por lo que la respuesta es $2$.

Para el tercer caso de prueba:

• Es fácil demostrar que es imposible hacer que todos los números sean iguales sin importar el número de operaciones, por lo que la respuesta es $-1$.