Sur le bureau d'Aya se trouve un collier de perles $a$ de longueur $n$. Chaque perle possède une valeur d'éclat, et la valeur d'éclat de la $i$-ième perle, du début à la fin, est notée $a_i$.
Aya tient un collier de perles $b$, initialement vide. Elle effectue plusieurs opérations sur ce collier. Lors de la $i$-ième opération, elle peut choisir l'une des deux actions suivantes :
- Ajouter une perle d'éclat $i$ à la fin du collier $b$.
- Augmenter de $1$ la valeur d'éclat de n'importe quelle perle présente dans $b$.
Aya souhaite savoir : quel est le nombre minimum d'opérations nécessaires pour que le collier $b$ soit identique au collier $a$ ? S'il est impossible de rendre le collier $b$ identique au collier $a$, répondre $-1$.
Entrée
Le problème comporte plusieurs jeux de données. La première ligne contient un entier positif $T$ ($1 \le T \le 10^4$), représentant le nombre de jeux de données.
Pour chaque jeu de données : La première ligne contient un entier positif $n$ ($1 \le n \le 5 \times 10^5$), représentant la longueur du collier $a$. La deuxième ligne contient $n$ entiers positifs, le $i$-ième entier étant $a_i$ ($1 \le a_i \le 10^{12}$), représentant la valeur d'éclat de la $i$-ième perle de $a$.
La somme des $n$ sur l'ensemble des $T$ jeux de données ne dépasse pas $5 \times 10^5$.
Sortie
Pour chaque jeu de données : Afficher un seul entier sur une ligne, représentant le nombre minimum d'opérations. S'il est impossible de rendre le collier $b$ identique au collier $a$, afficher $-1$.
Exemples
Entrée 1
3 5 1 2 4 5 6 8 1 2 4 5 5 8 10 9 3 3 2 1
Sortie 1
6 13 -1
Remarque 1
Pour le premier jeu de données : Une séquence d'opérations permettant d'atteindre le résultat en 6 étapes est la suivante :
- Ajouter une perle d'éclat 1 à la fin de $b$.
- Ajouter une perle d'éclat 2 à la fin de $b$.
- Ajouter une perle d'éclat 3 à la fin de $b$.
- Augmenter de 1 la valeur d'éclat de la 3e perle de $b$.
- Ajouter une perle d'éclat 5 à la fin de $b$.
- Ajouter une perle d'éclat 6 à la fin de $b$.