Вам дана перестановка \(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\) целых чисел, разделенных пробелами, \(i\)-е из них должно быть равно стоимости расположения бомб на позициях \(q_1, q_2, \ldots, q_{i-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\).