D. Самая длинная подпоследовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$. Пусть $$$S$$$ — множество всех непустых подпоследовательностей $$$a$$$, в которых нет одинаковых элементов. Ваша цель — найти самую длинную последовательность в $$$S$$$. Если таких несколько, найдите ту, которая минимизирует лексикографический порядок после умножения членов в нечетных позициях на $$$-1$$$.

Например, при $$$a = [3, 2, 3, 1]$$$, $$$S = \{[1], [2], [3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 3, 1], [3, 2, 1]\}$$$. Тогда $$$[2, 3, 1]$$$ и $$$[3, 2, 1]$$$ будут самыми длинными, а $$$[3, 2, 1]$$$ будет ответом, так как $$$[-3, 2, -1]$$$ лексикографически меньше, чем $$$[-2, 3, -1]$$$.

Последовательность $$$c$$$ является подпоследовательностью последовательности $$$d$$$, если $$$c$$$ может быть получена из $$$d$$$ путем удаления нескольких (возможно, нуля или всех) элементов.

Последовательность $$$c$$$ лексикографически меньше последовательности $$$d$$$ тогда и только тогда, когда выполняется одно из следующих условий:

  • $$$c$$$ является префиксом $$$d$$$, но $$$c \ne d$$$;
  • в первой позиции, где $$$c$$$ и $$$d$$$ различаются, последовательность $$$c$$$ имеет меньший элемент, чем соответствующий элемент в $$$d$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длина $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — последовательность $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите ответ в следующем формате:

Выведите целое число $$$m$$$ в первой строке — длину $$$b$$$.

Затем выведите $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ во второй строке — последовательность $$$b$$$.

Примеры
Входные данные
4
4
3 2 1 3
4
1 1 1 1
9
3 2 1 3 2 1 3 2 1
1
1
Выходные данные
3
3 2 1
1
1
3
3 1 2
1
1
Входные данные
10
2
1 2
10
5 2 1 7 9 7 2 5 5 2
2
1 2
10
2 2 8 7 7 9 8 1 9 6
9
9 1 7 5 8 5 6 4 1
3
3 3 3
6
1 6 4 4 6 5
6
3 4 4 5 3 3
10
4 1 4 5 4 5 10 1 5 1
7
1 2 1 3 2 4 6
Выходные данные
2
1 2
5
5 1 9 7 2
2
1 2
6
2 7 9 8 1 6
7
9 1 7 5 8 6 4
1
3
4
1 4 6 5
3
4 5 3
4
5 4 10 1
5
2 1 3 4 6
Примечание

В первом примере $$$S = \{[1], [2], [3], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 1, 3], [3, 2, 1]\}$$$. Среди них $$$[2, 1, 3]$$$ и $$$[3, 2, 1]$$$ — самые длинные, а $$$[-3, 2, -1]$$$ лексикографически меньше $$$[-2, 1, -3]$$$, поэтому $$$[3, 2, 1]$$$ — ответ.

Во втором примере $$$S = \{[1]\}$$$, поэтому $$$[1]$$$ — ответ.