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

Задана последовательность $$$a_1, a_2, \dots, a_n$$$. Вы можете выбрать любое подмножество элементов, после нужно переупорядочить их так, чтобы получилась «пила».

Последовательность $$$b_1, b_2, \dots, b_m$$$ называется «пилой», если элементы удовлетворяют неравенствам: $$$b_1>b_2<b_3>b_4<\dots$$$ или $$$b_1<b_2>b_3<b_4>\dots$$$.

Найдите максимальную по длине пилу, которую можно получить из заданного массива.

Заметим, что и заданная последовательность $$$a$$$ и искомая «пила» $$$b$$$ могут содержать неуникальные (то есть такие, которые встречаются дважды или более) значения.

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

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$t$$$ наборов входных данных теста. Каждый набор начинается со строки, содержащей целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$). Затем следует строка, содержащая $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что $$$\sum{n}$$$ не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите две строки: в первую строку выведите длину наидлиннейшей пилы, во вторую строку — саму пилу. Если решений несколько, выведите любое из них.

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