Alice และ Bob มีการ์ด $2n$ ใบ แต่ละใบมีจำนวนเต็มเขียนอยู่ โดยที่แต่ละจำนวนเต็มระหว่าง $1$ ถึง $n$ จะปรากฏบนการ์ดสองใบพอดี เริ่มต้น Alice และ Bob ถือการ์ดคนละ $n$ ใบ
พวกเขากำลังจะเล่นเกมการ์ดโดยให้ Alice เริ่มก่อน ในแต่ละเทิร์น ผู้เล่นในเทิร์นนั้นจะวางการ์ดจากมือของตนลงบนด้านบนสุดของกองการ์ด หากตอนนี้มีการ์ดสองใบที่มีหมายเลขเดียวกันอยู่ในกอง ผู้เล่นในเทิร์นนั้นจะได้ $1$ คะแนน และนำการ์ดสองใบที่ตรงกันพร้อมกับการ์ดทั้งหมดที่อยู่ระหว่างการ์ดสองใบนั้นออกจากกอง ไปไว้ในกองทิ้งการ์ด
เมื่อกำหนดลำดับการเล่นของ Alice แล้ว Bob จะจัดลำดับการเล่นของเขาอย่างไรเพื่อให้คะแนนของ Alice น้อยที่สุด?
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^5$) แทนจำนวนกรณีทดสอบ
สำหรับแต่ละกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 5 \times 10^5$)
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน ได้แก่ $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) แทนหมายเลขบนการ์ดที่ Alice เล่นตามลำดับ รับประกันว่าไม่มีหมายเลขใดปรากฏเกินสองครั้งใน $a_i$
รับประกันว่าผลรวมของ $n$ ในทุกกรณีทดสอบจะไม่เกิน $5 \times 10^5$
ข้อมูลส่งออก
สำหรับแต่ละกรณีทดสอบ บรรทัดแรกของข้อมูลส่งออกควรประกอบด้วยจำนวนเต็มหนึ่งจำนวน แทนคะแนนน้อยที่สุดที่ Alice สามารถทำได้
บรรทัดที่สองควรประกอบด้วยจำนวนเต็ม $n$ จำนวน ได้แก่ $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) แทนการเล่นของ Bob ตามลำดับ โดยที่แต่ละจำนวนเต็มตั้งแต่ $1$ ถึง $n$ จะปรากฏสองครั้งพอดีในลำดับที่รวมกันของ $a_i$ และ $b_i$
ตัวอย่าง
ข้อมูลนำเข้า
3 3 1 2 3 5 3 1 4 1 5 5 1 4 5 1 4
ข้อมูลส่งออก
0 1 2 3 0 2 3 2 4 5 1 3 2 2 3 5
หมายเหตุ
สำหรับกรณีทดสอบที่สาม เกมดำเนินไปดังนี้:
| ขั้นตอน | ผู้เล่น | การ์ดที่เล่น | กองการ์ดจากล่างขึ้นบน | คะแนนของ Alice | คะแนนของ 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$ |