У Алисы и Боба есть $2n$ карт, на каждой из которых написано целое число, причём каждое целое число от $1$ до $n$ встречается ровно на двух картах. Изначально у Алисы и Боба на руках по $n$ карт.
Они собираются сыграть в карточную игру; первой ходит Алиса. В каждый ход текущий игрок кладёт карту со своей руки наверх стопки. Если после этого в стопке оказываются две карты с одинаковым числом, текущий игрок получает $1$ очко и забирает эти две совпадающие карты вместе со всеми картами между ними, отправляя их в сброс.
Зная последовательность ходов Алисы, как Бобу спланировать свои ходы, чтобы минимизировать количество очков Алисы?
Входные данные
Первая строка содержит целое число $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$) — числа на картах, которые по порядку выкладывает Алиса. Гарантируется, что ни одно число не встречается в $a_i$ более двух раз.
Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $5 \times 10^5$.
Выходные данные
Для каждого набора входных данных в первой строке выведите одно целое число — минимальное количество очков, которое может набрать Алиса.
Во второй строке выведите $n$ целых чисел $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), обозначающих ходы Боба по порядку, так, чтобы каждое целое число от $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
Примечание
В третьем наборе входных данных игра проходит следующим образом:
| Шаг | Игрок | Сыгранная карта | Стопка снизу вверх | Очки Алисы | Очки Боба |
|---|---|---|---|---|---|
| $1$ | Алиса | $1$ | $[1]$ | $0$ | $0$ |
| $2$ | Боб | $3$ | $[1, 3]$ | $0$ | $0$ |
| $3$ | Алиса | $4$ | $[1, 3, 4]$ | $0$ | $0$ |
| $4$ | Боб | $2$ | $[1, 3, 4, 2]$ | $0$ | $0$ |
| $5$ | Алиса | $5$ | $[1, 3, 4, 2, 5]$ | $0$ | $0$ |
| $6$ | Боб | $2$ | $[1, 3, 4]$ | $0$ | $1$ |
| $7$ | Алиса | $1$ | $[]$ | $1$ | $1$ |
| $8$ | Боб | $3$ | $[3]$ | $1$ | $1$ |
| $9$ | Алиса | $4$ | $[3, 4]$ | $1$ | $1$ |
| $10$ | Боб | $5$ | $[3, 4, 5]$ | $1$ | $1$ |