E. Бомбы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p_1, p_2, \ldots, p_n$$$.

Представим, что некоторые позиции этой перестановки содержат бомбы, причем существует хотя бы одна позиция без бомбы.

Для фиксированного расположения бомб, рассмотрим следующий процесс с пустым изначально множеством $$$A$$$.

Для всех $$$i$$$ от $$$1$$$ до $$$n$$$:

  • Добавить $$$p_i$$$ в $$$A$$$.
  • Если $$$i$$$-я позиция содержит бомбу, удалить максимальный элемент из $$$A$$$.

После конца этого процесса, $$$A$$$ будет непусто. Стоимость расположения бомб равно наибольшему элементу в $$$A$$$.

Вам дана еще одна перестановка, $$$q_1, q_2, \ldots, q_n$$$.

Для всех $$$1 \leq i \leq n$$$, найдите стоимость расположения бомб на позициях $$$q_1, q_2, \ldots, q_{i-1}$$$.

Например, для $$$i=1$$$, вам необходимо найти стоимость расположения без бомб, а для $$$i=n$$$, вам нужно найти стоимость расположения бомб на позициях $$$q_1, q_2, \ldots, q_{n-1}$$$.

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

В первой строке записано целое число $$$n$$$ ($$$2 \leq n \leq 300\,000$$$).

Во второй строке записано $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n)$$$.

В третьей строке записано $$$n$$$ различных целых чисел $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \leq q_i \leq n)$$$.

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

Выведите $$$n$$$ целых чисел, разделенных пробелами, $$$i$$$-е из них должно быть равно стоимости расположения бомб на позициях $$$q_1, q_2, \ldots, q_{i-1}$$$.

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

В первом тесте:

  • Если бомб нет, $$$A$$$ будет равно $$$\{1, 2, 3\}$$$ в конце процесса, и стоимость расположения равна $$$3$$$.
  • Если есть одна бомба на позиции $$$1$$$, $$$A$$$ будет равно $$$\{1, 2\}$$$ в конце процесса, соответственно стоимость расположения равна $$$2$$$;
  • Если есть две бомбы на позициях $$$1$$$ и $$$2$$$, $$$A$$$ будет равно $$$\{1\}$$$ в конце процесса, и стоимость расположения равна $$$1$$$.

Во втором тесте:

Рассмотрим процесс для $$$i = 4$$$. Есть три бомбы на позициях $$$q_1 = 5$$$, $$$q_2 = 2$$$, и $$$q_3 = 1$$$.

В начале, $$$A = \{\}$$$.

  • Операция $$$1$$$: Добавить $$$p_1 = 2$$$ в $$$A$$$, таким образом $$$A$$$ равно $$$\{2\}$$$. Существует бомба на позиции $$$1$$$, так что мы должны удалить максимальный элемент из $$$A$$$. $$$A$$$ равно $$$\{\}$$$.
  • Операция $$$2$$$: Добавить $$$p_2 = 3$$$ в $$$A$$$, таким образом $$$A$$$ равно $$$\{3\}$$$. Существует бомба на позиции $$$2$$$, так что нам нужно удалить максимальный элемент из $$$A$$$. $$$A$$$ равно $$$\{\}$$$.
  • Операция $$$3$$$: Добавить $$$p_3 = 6$$$ в $$$A$$$, таким образом $$$A$$$ равно $$$\{6\}$$$. На позиции $$$3$$$ нет бомбы, соответственно делать ничего не требуется.
  • Операция $$$4$$$: Добавить $$$p_4 = 1$$$ в $$$A$$$, таким образом $$$A$$$ равно $$$\{1, 6\}$$$. На позиции $$$4$$$ нет бомбы, соответственно делать ничего не требуется.
  • Операция $$$5$$$: Добавить $$$p_5 = 5$$$ в $$$A$$$, таким образом $$$A$$$ равно $$$\{1, 5, 6\}$$$. Существует бомба на позиции $$$5$$$, так что нам нужно удалить максимальный элемент из $$$A$$$. $$$A$$$ равно $$$\{1, 5\}$$$.
  • Операция $$$6$$$: Добавить $$$p_6 = 4$$$ в $$$A$$$, таким образом $$$A$$$ равно $$$\{1, 4, 5\}$$$. На позиции $$$6$$$ нет бомбы, соответственно делать ничего не требуется.

В конце $$$A = \{1, 4, 5\}$$$, соответственно стоимость расположения равна $$$5$$$.