E. Наибольшая возрастающая подпоследовательность
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на то, что ограничение по памяти в этой задаче меньше обычного

Рассмотрим массив, состоящий из целых положительных чисел, на некоторых местах которого находятся пропуски.

Имеется набор чисел, которые можно использовать для заполнения пропусков. Каждое число из данного набора может быть использовано максимум один раз.

Требуется определить такой способ заполнения пропусков, в котором наибольшая возрастающая подпоследовательность в образованном массиве имеет максимально возможный размер.

Входные данные

В первой строке находится одно целое число n — длина массива (1 ≤ n ≤ 105).

Во второй строке находятся n целых чисел, разделённых пробелами — элементы последовательности. Пропуск обозначается как "-1". Элементы, не являющиеся пропусками, — положительные целые числа, не превосходящие 109. Гарантируется, что последовательность содержит k ≤ 1000 пропусков.

В третьей строке находится одно положительное целое число m — количество элементов для заполнения пропусков (0 ≤ k ≤ m ≤ 105).

В четвертой строке находятся m целых положительных чисел — числа для заполнения пропусков. Каждое число — положительное целое, не превосходящее 109. Среди них могут быть совпадающие.

Выходные данные

Выведите n чисел в одной строке через пробел — полученную последовательность. Если возможных ответов несколько, выведите любой из них.

Примеры
Входные данные
3
1 2 3
1
10
Выходные данные
1 2 3
Входные данные
3
1 -1 3
3
1 2 3
Выходные данные
1 2 3
Входные данные
2
-1 2
2
2 4
Выходные данные
2 2
Входные данные
3
-1 -1 -1
5
1 1 1 1 2
Выходные данные
1 1 2
Входные данные
4
-1 -1 -1 2
4
1 1 2 2
Выходные данные
1 2 1 2
Примечание

В первом примере пропусков нет, поэтому правильный ответ — исходная последовательность.

Во втором примере есть только один способ получить возрастающую подпоследовательность длины 3.

В третьем примере ответ "4 2" тоже был бы верным. Обратите внимание, что рассматриваются только строго возрастающие подпоследовательности.

В пятом примере ответ "1 1 1 2" верным не является, так как число 1 можно использовать на замену только два раза.