Вам дан массив \(a\) из \(n\) целых положительных чисел, а также массив \(b\) из \(m\) целых положительных чисел.
Пусть \(\text{LIS}(c)\) обозначает длину самой длинной строго возрастающей подпоследовательности массива \(c\). Например, \(\text{LIS}([2, \underline{1}, 1, \underline{3}])\) = \(2\), \(\text{LIS}([\underline{1}, \underline{7}, \underline{9}])\) = \(3\), \(\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])\) = \(3\).
Вам нужно вставить числа \(b_1, b_2, \ldots, b_m\) в массив \(a\), в любые места, в любом порядке. Пусть после вставки массив будет равен \(c_1, c_2, \ldots, c_{n+m}\). Вам нужно выбрать места для вставки так, чтобы минимизировать \(\text{LIS}(c)\).
Формально, вам нужно найти такой массив \(c_1, c_2, \ldots, c_{n+m}\), для которого одновременно выполняются следующие условия:
- Массив \(a_1, a_2, \ldots, a_n\) является подпоследовательностью массива \(c_1, c_2, \ldots, c_{n+m}\).
- Массив \(c_1, c_2, \ldots, c_{n+m}\) состоит из чисел \(a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m\), возможно, переставленных в другом порядке.
- Значение \(\text{LIS}(c)\) минимально возможное среди всех подходящих массивов \(c\).
Выходные данные
Для каждого набора входных данных выведите \(n + m\) чисел — элементы итогового массива \(c_1, c_2, \ldots, c_{n+m}\), для которого значение \(\text{LIS}(c)\) является минимальным из возможных. Если подходящих массивов несколько, вы можете вывести любой из них.
Примечание
В первом наборе входных данных \(\text{LIS}(a) = \text{LIS}([6, 4]) = 1\). Можно вставить число \(5\) между \(6\) и \(4\), тогда \(\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1\).
Во втором наборе входных данных \(\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}])\) = \(4\). После вставки, \(c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5]\). Несложно видеть, что \(\text{LIS}(c) = 4\). Можно показать, что значения \(\text{LIS}(c)\), меньшего чем \(4\), добиться невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777
|
6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1
|