B. Автобус характеров
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В автобусе характеров есть $$$n$$$ рядов сидений, в каждом по $$$2$$$ места. В $$$i$$$-м ряду ширина обоих сидений равна $$$w_i$$$ сантиметров. Все числа $$$w_i$$$ различны.

Изначально автобус пустой. На каждой из $$$2n$$$ остановок в автобус садится ровно один человек одного из двух характеров:

  • интроверт всегда выбирает ряд, где оба места свободны, при этом из таких рядов он выбирает ряд с самыми узкими сидениями, и занимает одно место;
  • экстраверт всегда выбирает ряд, где уже сидит один человек (интроверт), при этом из таких рядов он выбирает ряд с самыми широкими сидениями, и занимает оставшееся в выбранном ряду место.

Вам дана ширина сидений в каждом ряду, а также порядок, в котором входили пассажиры. Определите, на какой ряд сядет каждый из пассажиров.

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

В первой строке следует целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — количество рядов сидений в автобусе.

Во второй строке следует последовательность целых чисел $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 10^{9}$$$), где $$$w_i$$$ равно ширине каждого из двух сидений в $$$i$$$-м ряду. Гарантируется, что все $$$w_i$$$ различны.

В третьей строке следует строка длины $$$2n$$$, состоящая из символов «0» и «1» — описание порядка, в котором пассажиры заходят в автобус. Если $$$j$$$-й символ строки равен «0», то на $$$j$$$-й остановке в автобус зашел интроверт. Если $$$j$$$-й символ строки равен «1», то на $$$j$$$-й остановке в автобус зашел экстраверт. Гарантируется, что интровертов и экстравертов, которые зашли в автобус, поровну (то есть по $$$n$$$), и для каждого экстраверта всегда найдется подходящий ряд.

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

Выведите $$$2n$$$ целых чисел — номера рядов, в которые сели пассажиры. Номера рядов для пассажиров должны быть выведены в том же порядке, в котором пассажиры заданы во входных данных.

Примеры
Входные данные
2
3 1
0011
Выходные данные
2 1 1 2
Входные данные
6
10 8 9 11 13 5
010010011101
Выходные данные
6 6 2 3 3 1 4 4 1 2 5 5
Примечание

В первом примере первый пассажир (интроверт) выберет ряд номер $$$2$$$, так как в нем самые узкие сиденья. Второй пассажир (интроверт) выберет ряд номер $$$1$$$, так как это единственный оставшийся пустой ряд. Третий пассажир (экстраверт) выберет ряд номер $$$1$$$, так как в нем уже сидит один пассажир и этот ряд самый широкий. Четвертый пассажир (экстраверт) выберет ряд номер $$$2$$$, так как это единственный ряд, в котором осталось свободное место.