Для заданной перестановки \(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\) встречается ровно один раз.
Выходные данные
Для каждого набора входных данных первая строка должна содержать длину найденной подпоследовательности, \(k\). Вторая строка должна содержать \(s_1\), \(s_2\), \(\ldots\), \(s_k\) — ее элементы.
Если несколько подпоследовательностей удовлетворяют этим условиям, вы можете найти любую из них.
Примечание
В первом тестовом примере есть \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
3 2 1
4
1 3 4 2
|
2
3 1
3
1 4 2
|