Вам дана последовательность целых чисел \(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\).
Выходные данные
Для каждого набора входных данных выведите ответ в следующем формате:
Выведите целое число \(m\) в первой строке — длину \(b\).
Затем выведите \(m\) целых чисел \(b_1, b_2, \ldots, b_m\) во второй строке — последовательность \(b\).
Примечание
В первом примере \(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]\) — ответ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|