Alice und Bob haben $2n$ Karten, auf denen jeweils eine ganze Zahl steht, sodass jede ganze Zahl zwischen $1$ und $n$ auf genau zwei Karten vorkommt. Zu Beginn halten Alice und Bob jeweils $n$ Karten auf der Hand.
Sie spielen ein Kartenspiel, bei dem Alice beginnt. In jedem Zug legt der aktuelle Spieler eine Karte aus seiner Hand oben auf den Stapel. Wenn sich nun zwei Karten mit derselben Zahl im Stapel befinden, erhält der aktuelle Spieler $1$ Punkt und entfernt die beiden übereinstimmenden Karten zusammen mit allen dazwischenliegenden Karten und legt sie auf den Ablagestapel.
Wie kann Bob angesichts der Zugfolge von Alice seine Züge anordnen, um die Punktzahl von Alice zu minimieren?
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die Anzahl der Testfälle.
Für jeden Testfall enthält die erste Zeile eine ganze Zahl $n$ ($1 \le n \le 5 \times 10^5$).
Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), die der Reihe nach die Zahlen auf den von Alice gespielten Karten darstellen. Es wird garantiert, dass keine Zahl mehr als zweimal in $a_i$ vorkommt.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $5 \times 10^5$ nicht überschreitet.
Ausgabe
Für jeden Testfall sollte die erste Zeile der Ausgabe eine ganze Zahl enthalten, die die minimale Punktzahl darstellt, die Alice erreichen kann.
Die zweite Zeile sollte $n$ ganze Zahlen $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) enthalten, die Bobs Züge der Reihe nach darstellen, sodass jede ganze Zahl von $1$ bis $n$ in den kombinierten Folgen von $a_i$ und $b_i$ genau zweimal vorkommt.
Beispiel
Eingabe
3 3 1 2 3 5 3 1 4 1 5 5 1 4 5 1 4
Ausgabe
0 1 2 3 0 2 3 2 4 5 1 3 2 2 3 5
Hinweis
Für den dritten Testfall verläuft das Spiel wie folgt:
| Schritt | Spieler | Gespielte Karte | Stapel von unten nach oben | Punkte von Alice | Punkte von 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$ |