Обратите внимание на то, что ограничение по памяти в этой задаче меньше обычного
Рассмотрим массив, состоящий из целых положительных чисел, на некоторых местах которого находятся пропуски.
Имеется набор чисел, которые можно использовать для заполнения пропусков. Каждое число из данного набора может быть использовано максимум один раз.
Требуется определить такой способ заполнения пропусков, в котором наибольшая возрастающая подпоследовательность в образованном массиве имеет максимально возможный размер.
Выходные данные
Выведите n чисел в одной строке через пробел — полученную последовательность. Если возможных ответов несколько, выведите любой из них.
Примечание
В первом примере пропусков нет, поэтому правильный ответ — исходная последовательность.
Во втором примере есть только один способ получить возрастающую подпоследовательность длины 3.
В третьем примере ответ "4 2" тоже был бы верным. Обратите внимание, что рассматриваются только строго возрастающие подпоследовательности.
В пятом примере ответ "1 1 1 2" верным не является, так как число 1 можно использовать на замену только два раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
1
10
|
1 2 3
|
|
2
|
3
1 -1 3
3
1 2 3
|
1 2 3
|
|
3
|
2
-1 2
2
2 4
|
2 2
|
|
4
|
3
-1 -1 -1
5
1 1 1 1 2
|
1 1 2
|
|
5
|
4
-1 -1 -1 2
4
1 1 2 2
|
1 2 1 2
|