Alice và Bob có $2n$ lá bài, mỗi lá bài được ghi một số nguyên sao cho mỗi số nguyên từ $1$ đến $n$ xuất hiện trên đúng hai lá bài. Ban đầu, Alice và Bob mỗi người cầm $n$ lá bài.
Họ chuẩn bị chơi một trò chơi thẻ bài, với Alice là người đi trước. Ở mỗi lượt, người chơi hiện tại đặt một lá bài trên tay lên đỉnh của chồng bài. Nếu lúc này trong chồng bài có hai lá bài mang cùng một số, người chơi hiện tại sẽ ghi được $1$ điểm và lấy hai lá bài trùng nhau đó cùng với tất cả các lá bài nằm giữa chúng ra khỏi chồng bài, đặt vào chồng bài bỏ.
Cho trước trình tự các nước đi của Alice, Bob có thể sắp xếp các nước đi của mình như thế nào để cực tiểu hóa điểm số của Alice?
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^5$), cho biết số lượng bộ dữ liệu.
Với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 5 \times 10^5$).
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), biểu thị các số trên các lá bài mà Alice đánh ra theo thứ tự. Dữ liệu đảm bảo không có số nào xuất hiện quá hai lần trong $a_i$.
Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $5 \times 10^5$.
Dữ liệu ra
Với mỗi bộ dữ liệu, dòng đầu tiên in ra một số nguyên biểu thị điểm số nhỏ nhất mà Alice có thể đạt được.
Dòng thứ hai in ra $n$ số nguyên $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), biểu thị các nước đi của Bob theo thứ tự, sao cho mỗi số nguyên từ $1$ đến $n$ xuất hiện đúng hai lần trong dãy kết hợp của $a_i$ và $b_i$.
Ví dụ
Dữ liệu vào
3 3 1 2 3 5 3 1 4 1 5 5 1 4 5 1 4
Dữ liệu ra
0 1 2 3 0 2 3 2 4 5 1 3 2 2 3 5
Ghi chú
Đối với bộ dữ liệu thứ ba, trò chơi diễn ra như sau:
| Bước | Người chơi | Lá bài đã đánh | Chồng bài từ dưới lên trên | Điểm của Alice | Điểm của 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$ |