E. Мадока и шестиклассики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После ошеломительного успеха у пятого класса, Мадоке решили доверить преподавать уже шестиклассникам.

Всего в её классе есть $$$n$$$ одноместных парт. Изначально Мадока за $$$i$$$-ю парту посадила ученика под номером $$$b_i$$$ ($$$1 \le b_i \le n$$$), а за дверью образовалась бесконечная очередь учеников с номерами $$$n + 1, n + 2, n + 3, \ldots$$$ в надежде оказаться на её уроке. Обратите внимание, что все ученики имеют различные номера.

После каждого урока происходит следующие события по порядку.

  1. Ученик, сидевший за партой $$$i$$$, перемещается за парту $$$p_i$$$. Все ученики перемещаются одновременно.
  2. Если за какой-то партой оказалось больше одного ученика, то за ней остается ученик с наименьшим номером, а все остальные навсегда покидают класс.
  3. Затем на каждую пустую парту в порядке возрастания номеров садится ученик с наименьшим номером из очереди снаружи.

Обратите внимание, что в итоге за каждой партой снова находится ровно один ученик. Гарантируется, что числа $$$p$$$ таковы, что как минимум один ученик покидает класс после каждого урока. Обратите внимание на пояснение к первому примеру для лучшего понимания.

После нескольких (возможно нуля) уроков за партой $$$i$$$ сидит ученик $$$a_i$$$. По данным значениям $$$a_1, a_2, \ldots, a_n$$$ и $$$p_1, p_2, \ldots, p_n$$$, найдите лексикографически наименьшую подходящую перестановку $$$b_1, b_2, \ldots, b_n$$$, описывающую возможную начальную рассадку.

Перестановкой называется массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ встречается дважды в массиве) и $$$[1,3,4]$$$ тоже не является перестановкой ($$$n=3$$$, но $$$4$$$ присутствует в массиве).

Для двух различных перестановок равной длины $$$a$$$ и $$$b$$$, $$$a$$$ лексикографически меньше $$$b$$$, если в первой позиции, где $$$a$$$ и $$$b$$$ различны, в $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.

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

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество парт в классе.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — места, куда пересаживаются ученики. Гарантируется, что $$$p$$$ содержит хотя бы два равных элемента.

Третья строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — конечная рассадка учеников. Гарантируется, что существует изначальная перестановка, из которой получилась рассадка $$$a$$$.

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

В единственной строке выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — лексикографически минимальную перестановку, описывающую начальную рассадку учеников, из которой могла получится конечная рассадка $$$a$$$.

Примеры
Входные данные
5
5 5 3 3 1
1 8 2 9 4
Выходные данные
1 3 2 5 4 
Входные данные
5
1 3 2 5 2
3 2 5 4 1
Выходные данные
3 2 5 4 1 
Входные данные
10
10 8 5 3 7 8 6 6 1 1
5 26 24 27 21 4 18 2 28 1
Выходные данные
5 4 2 6 7 8 3 9 1 10 
Примечание

Описание первого теста находится ниже:

На первой картинке показана стартовая рассадка, являющаяся ответом. Затем ученики, сидящие за партами $$$1, 2$$$ пересаживаются за $$$5$$$ парту. Также за $$$1$$$ парту пересел ученик с парты $$$5$$$, а за парту под номером $$$3$$$ пересаживается ученик с $$$4$$$ парты.

Таким образом, после всех этих пересадок, получается рассадка, показаная на втором изображении. Затем за партой под номером $$$5$$$ выгоняют ученика с номером $$$3$$$, а за партой под номером $$$3$$$ выгоняют ученика с номером $$$5$$$. (Поскольку их номера не самые маленькие) Затем за парты под номерами $$$2, 4$$$ садятся новые ученики с номерами $$$6, 7$$$. И эта рассадка (после конца первого урока) показана на третьем изображении.

На $$$4$$$ изображении показана рассадка, после второго урока до того, как всех лишних выгнали. А на пятой показана финальная рассадка после $$$2$$$ урока.