Aya tiene sobre su escritorio un collar de perlas $a$ de longitud $n$. Cada perla tiene un valor de brillo, y el valor de brillo de la $i$-ésima perla desde el principio hasta el final es $a_i$.

Aya sostiene en su mano un collar de perlas $b$, inicialmente vacío. Ella realiza varias operaciones sobre este collar; en la $i$-ésima operación, puede elegir una de las siguientes dos opciones:

• Añadir una perla con un valor de brillo de $i$ al final de $b$.
• Aumentar el valor de brillo de cualquier perla en $b$ en $1$.

Aya quiere saber: ¿cuál es el número mínimo de operaciones necesarias para que el collar de perlas $b$ sea exactamente igual a $a$? Si no es posible hacer que el collar de perlas $b$ sea exactamente igual a $a$, responda $-1$.

Entrada

Este problema contiene múltiples casos de prueba. La primera línea contiene un entero positivo $T$ ($1 \le T \le 10^4$), que indica 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 5 \times 10^5$), que indica la longitud del collar de perlas $a$. La segunda línea contiene $n$ enteros positivos, donde el $i$-ésimo entero es $a_i$ ($1 \le a_i \le 10^{12}$), que representa el valor de brillo de la $i$-ésima perla de $a$ desde el principio hasta el final.

Se garantiza que la suma de $n$ en los $T$ casos de prueba no supera $5 \times 10^5$.

Salida

Para cada caso de prueba: Imprima una línea con un solo entero que represente el número mínimo de operaciones. Si no es posible hacer que el collar de perlas $b$ sea exactamente igual a $a$, imprima $-1$.

Ejemplos

Entrada 1

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

Salida 1

6
13
-1

Nota 1

Para el primer caso de prueba: El plan con $6$ operaciones es el siguiente:

1. Añadir una perla con valor de brillo $1$ al final de $b$.
2. Añadir una perla con valor de brillo $2$ al final de $b$.
3. Añadir una perla con valor de brillo $3$ al final de $b$.
4. Aumentar el valor de brillo de la $3$-era perla de $b$ (desde el principio) en $1$.
5. Añadir una perla con valor de brillo $5$ al final de $b$.
6. Añadir una perla con valor de brillo $6$ al final de $b$.