Alice et Bob ont $2n$ cartes, chacune portant un entier, de telle sorte que chaque entier compris entre $1$ et $n$ apparaisse sur exactement deux cartes. Initialement, Alice et Bob tiennent chacun $n$ cartes.
Ils vont jouer à un jeu de cartes, où Alice commence. À chaque tour, le joueur courant place une carte de sa main au sommet de la pile. S'il y a maintenant deux cartes avec le même numéro dans la pile, le joueur courant marque $1$ point et retire les deux cartes correspondantes ainsi que toutes les cartes situées entre elles, en les plaçant dans la défausse.
Étant donné la séquence de coups d'Alice, comment Bob peut-il organiser ses coups pour minimiser le score d'Alice ?
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 10^5$), indiquant le nombre de cas de test.
Pour chaque cas de test, la première ligne contient un entier $n$ ($1 \le n \le 5 \times 10^5$).
La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), représentant dans l'ordre les numéros sur les cartes jouées par Alice. Il est garanti qu'aucun numéro n'apparaît plus de deux fois dans $a_i$.
Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $5 \times 10^5$.
Sortie
Pour chaque cas de test, la première ligne de sortie doit contenir un entier, représentant le score minimal qu'Alice peut obtenir.
La deuxième ligne doit contenir $n$ entiers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), représentant dans l'ordre les coups de Bob, de sorte que chaque entier de $1$ à $n$ apparaisse exactement deux fois dans les séquences combinées de $a_i$ et $b_i$.
Exemple
Entrée
3 3 1 2 3 5 3 1 4 1 5 5 1 4 5 1 4
Sortie
0 1 2 3 0 2 3 2 4 5 1 3 2 2 3 5
Note
Pour le troisième cas de test, la partie se déroule comme suit :
| Étape | Joueur | Carte jouée | Pile du bas vers le haut | Score d'Alice | Score de Bob |
|---|---|---|---|---|---|
| $1$ | Alice | $1$ | $[1]$ | $0$ | $0$ |
| $2$ | Bob | $3$ | $[1, 3]$ | $0$ | $0$ |
| $3$ | Alice | $4$ | $[1, 3, 4]$ | $0$ | $0$ |
| $4$ | Bob | $2$ | $[1, 3, 4, 2]$ | $0$ | $0$ |
| $5$ | Alice | $5$ | $[1, 3, 4, 2, 5]$ | $0$ | $0$ |
| $6$ | Bob | $2$ | $[1, 3, 4]$ | $0$ | $1$ |
| $7$ | Alice | $1$ | $[]$ | $1$ | $1$ |
| $8$ | Bob | $3$ | $[3]$ | $1$ | $1$ |
| $9$ | Alice | $4$ | $[3, 4]$ | $1$ | $1$ |
| $10$ | Bob | $5$ | $[3, 4, 5]$ | $1$ | $1$ |