После ошеломительного успеха у пятого класса, Мадоке решили доверить преподавать уже шестиклассникам.
Всего в её классе есть \(n\) одноместных парт. Изначально Мадока за \(i\)-ю парту посадила ученика под номером \(b_i\) (\(1 \le b_i \le n\)), а за дверью образовалась бесконечная очередь учеников с номерами \(n + 1, n + 2, n + 3, \ldots\) в надежде оказаться на её уроке. Обратите внимание, что все ученики имеют различные номера.
После каждого урока происходит следующие события по порядку.
- Ученик, сидевший за партой \(i\), перемещается за парту \(p_i\). Все ученики перемещаются одновременно.
- Если за какой-то партой оказалось больше одного ученика, то за ней остается ученик с наименьшим номером, а все остальные навсегда покидают класс.
- Затем на каждую пустую парту в порядке возрастания номеров садится ученик с наименьшим номером из очереди снаружи.
Обратите внимание, что в итоге за каждой партой снова находится ровно один ученик. Гарантируется, что числа \(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\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le n\)) — лексикографически минимальную перестановку, описывающую начальную рассадку учеников, из которой могла получится конечная рассадка \(a\).
Примечание
Описание первого теста находится ниже:
На первой картинке показана стартовая рассадка, являющаяся ответом. Затем ученики, сидящие за партами \(1, 2\) пересаживаются за \(5\) парту. Также за \(1\) парту пересел ученик с парты \(5\), а за парту под номером \(3\) пересаживается ученик с \(4\) парты.
Таким образом, после всех этих пересадок, получается рассадка, показаная на втором изображении. Затем за партой под номером \(5\) выгоняют ученика с номером \(3\), а за партой под номером \(3\) выгоняют ученика с номером \(5\). (Поскольку их номера не самые маленькие) Затем за парты под номерами \(2, 4\) садятся новые ученики с номерами \(6, 7\). И эта рассадка (после конца первого урока) показана на третьем изображении.
На \(4\) изображении показана рассадка, после второго урока до того, как всех лишних выгнали. А на пятой показана финальная рассадка после \(2\) урока.