B. Наиболее социально-дистанцированная подпоследовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для заданной перестановки $$$p$$$ длины $$$n$$$, найдите ее подпоследовательность $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$ длины хотя бы $$$2$$$ такую, что:

  • $$$|s_1-s_2|+|s_2-s_3|+\ldots+|s_{k-1}-s_k|$$$ является максимально возможным среди всех подпоследовательностей $$$p$$$ длины хотя бы $$$2$$$.
  • среди всех таких подпоследовательностей выберите ту, длина которой $$$k$$$ как можно меньше.

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

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

Перестановка длины $$$n$$$ — это массив длины $$$n$$$, в котором каждый элемент от $$$1$$$ до $$$n$$$ встречается ровно один раз.

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

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Описание наборов входных данных приведено ниже.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_{n}$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$ попарно различны) — элементы перестановки $$$p$$$.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.

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

Для каждого набора входных данных первая строка должна содержать длину найденной подпоследовательности, $$$k$$$. Вторая строка должна содержать $$$s_1$$$, $$$s_2$$$, $$$\ldots$$$, $$$s_k$$$  — ее элементы.

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

Пример
Входные данные
2
3
3 2 1
4
1 3 4 2
Выходные данные
2
3 1 
3
1 4 2
Примечание

В первом тестовом примере есть $$$4$$$ подпоследовательности длиной не менее $$$2$$$:

  • $$$[3,2]$$$, что дает нам $$$|3-2|=1$$$.
  • $$$[3,1]$$$, что дает нам $$$|3-1|=2$$$.
  • $$$[2,1]$$$, что дает нам $$$|2-1|=1$$$.
  • $$$[3,2,1]$$$, что дает нам $$$|3-2|+|2-1|=2$$$.

Таким образом, ответ либо $$$[3,1]$$$, либо $$$[3,2,1]$$$. Поскольку мы хотим, чтобы подпоследовательность была как можно короче, ответ будет $$$[3,1]$$$.