Pour célébrer le fait qu'aucune équipe n'a résolu le problème « Queue Editor » lors des demi-finales de la 3e Universal Cup, Little Cyan Fish a imaginé un nouveau problème impliquant une file et... cette fois-ci, une pile ! Il possède $n$ boules numérotées de $1$ à $n$. Les boules sont initialement disposées dans une file, et il dispose également d'une pile vide. Tant que la file n'est pas vide, il effectue les étapes suivantes :

1. Retirer la boule située à l'avant de la file. Soit $x$ son étiquette.
2. Tant que la pile n'est pas vide et que l'étiquette de la boule à son sommet est strictement supérieure à $x$, retirer la boule au sommet de la pile et l'ajouter à l'arrière de la file. Les boules sont ajoutées dans l'ordre dans lequel elles sont retirées.
3. Empiler la boule étiquetée $x$ au sommet de la pile.

On peut montrer que la file devient vide après un nombre fini d'étapes. Trouvez le nombre total de fois où Little Cyan Fish empile une boule sur la pile avant que cela ne se produise.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un seul entier $n$ ($1 \le n \le 5 \times 10^5$), indiquant le nombre de boules. La deuxième ligne contient $n$ entiers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), indiquant les étiquettes des boules dans la file initiale, de l'avant vers l'arrière. Il est garanti que $a_1, a_2, \ldots, a_n$ forment une permutation de $1, 2, \ldots, n$.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $5 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un seul entier, indiquant le nombre total de fois où une boule est empilée sur la pile.

Exemples

Entrée 1

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

Sortie 1

1
3
5
4

Entrée 2

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

Sortie 2

6
15

Remarque

Dans le premier exemple, les séquences d'étiquettes empilées sur la pile sont $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ et $(3, 1, 2, 3)$ pour les quatre cas de test, respectivement. La figure dans l'énoncé illustre le troisième cas de test du premier exemple.

Dans le premier cas de test du deuxième exemple, la séquence d'étiquettes empilées est $(2, 3, 1, 3, 2, 3)$, donc la réponse est $6$. Dans le deuxième cas de test du deuxième exemple, la séquence est $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, donc la réponse est $15$.