Alicella ja Bobilla on $2n$ korttia, joista jokaiseen on kirjoitettu kokonaisluku siten, että jokainen kokonaisluku väliltä $1$ ja $n$ esiintyy täsmälleen kahdessa kortissa. Aluksi Alicella ja Bobilla on kummallakin kädessään $n$ korttia.
He aikovat pelata korttipeliä, jonka Alice aloittaa. Jokaisella vuorolla vuorossa oleva pelaaja asettaa yhden kortin kädestään pinon päälle. Jos pinossa on nyt kaksi korttia, joissa on sama luku, vuorossa oleva pelaaja saa $1$ pisteen ja poistaa nämä kaksi täsmäävää korttia sekä kaikki niiden välissä olevat kortit ja siirtää ne poistopinoon.
Kun Alicen siirtojen järjestys annetaan, miten Bob voi järjestää omat siirtonsa minimoidakseen Alicen pistemäärän?
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmaisee testitapausten lukumäärän.
Jokaisessa testitapauksessa ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 5 \times 10^5$).
Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), jotka kuvaavat Alicen pelaamien korttien lukuja järjestyksessä. On taattu, että mikään luku ei esiinny enempää kuin kaksi kertaa jonossa $a_i$.
On taattu, että lukujen $n$ summa kaikkien testitapausten yli ei ylitä arvoa $5 \times 10^5$.
Tuloste
Jokaista testitapausta kohden tulosteen ensimmäisen rivin tulee sisältää kokonaisluku, joka kuvaa pienintä pistemäärää, jonka Alice voi saada.
Toisen rivin tulee sisältää $n$ kokonaislukua $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), jotka kuvaavat Bobin siirtoja järjestyksessä siten, että jokainen kokonaisluku väliltä $1$ – $n$ esiintyy täsmälleen kaksi kertaa jonojen $a_i$ ja $b_i$ yhdistelmässä.
Esimerkki
Syöte
3 3 1 2 3 5 3 1 4 1 5 5 1 4 5 1 4
Tuloste
0 1 2 3 0 2 3 2 4 5 1 3 2 2 3 5
Huomautus
Kolmannessa testitapauksessa peli etenee seuraavasti:
| Vaihe | Pelaaja | Pelattu kortti | Pino alhaalta ylös | Alicen pisteet | Bobin pisteet |
|---|---|---|---|---|---|
| $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$ |