Задача 1: Ракета на старт
Сергей собирает многоступенчатые ракеты. Для большей точности измерений параметров полета на каждой ступени ракеты он написал её мощность.

Но он совершенно забыл, что мощности ступеней любой ракеты должны строго возрастать. К примеру, мощности ступеней ракеты могут принимать значения 1 4 7, а 3 2 4 — не могут.

Собирать новую ракету Серёжа не хочет, однако он может вытащить некоторые ступени, не меняя порядка оставшихся. К примеру, из ракеты с мощностями ступеней 1 8 3 4 можно получить ракету 1 3 4 (вытащив ступень с мощностью 8), а ракеты 1 4 3 (порядок ступеней с мощностями 4 и 3 был изменен) и 1 8 3 (мощности ступеней не возрастают) получить нельзя.

Помогите Сергею вытащить минимальное количество ступеней так, чтобы мощность остальных ступеней строго возрастала.

У Сергея есть четыре ракеты. В таблице ниже для каждой ракеты приведена последовательность мощностей её ступеней.

Номер ракеты

Последовательность мощностей

1

5 3 4 2 3

2

1 6 3 2 5 8

3

4 6 7 5 6 7 1 2 8

4

2 5 3 5 3 4 7 3 8 4 9 6 7

Ответом на данную задачу являются четыре последовательности целых чисел: каждая из них — это последовательность мощностей оставшихся ступеней соответствующей ракеты. Каждую последовательность записывайте в соответствующей ей строке. Числа в последовательности должны быть разделены пробелом. Каждая последовательность должна строго возрастать, а также иметь как можно большую длину. Если существует несколько вариантов ответа, можно вывести любой из них.

Если вы не можете дать ответ для какой-то из ракет, запишите в качестве ответа для данной ракеты число 0.

Примечание. Рассмотрим пример. Допустим, у какой-то ракеты последовательность ступеней равна 1 4 5 2 3.


Для этой ракеты возможно два варианта ответа. Последовательность чисел в ответе может быть такой: 1 2 3. Или последовательность чисел может быть такой: 1 4 5.


В ответе нужно указать одну, любую из этих последовательностей.

Сдать решение