В автобусе характеров есть \(n\) рядов сидений, в каждом по \(2\) места. В \(i\)-м ряду ширина обоих сидений равна \(w_i\) сантиметров. Все числа \(w_i\) различны.
Изначально автобус пустой. На каждой из \(2n\) остановок в автобус садится ровно один человек одного из двух характеров:
- интроверт всегда выбирает ряд, где оба места свободны, при этом из таких рядов он выбирает ряд с самыми узкими сидениями, и занимает одно место;
- экстраверт всегда выбирает ряд, где уже сидит один человек (интроверт), при этом из таких рядов он выбирает ряд с самыми широкими сидениями, и занимает оставшееся в выбранном ряду место.
Вам дана ширина сидений в каждом ряду, а также порядок, в котором входили пассажиры. Определите, на какой ряд сядет каждый из пассажиров.
Выходные данные
Выведите \(2n\) целых чисел — номера рядов, в которые сели пассажиры. Номера рядов для пассажиров должны быть выведены в том же порядке, в котором пассажиры заданы во входных данных.
Примечание
В первом примере первый пассажир (интроверт) выберет ряд номер \(2\), так как в нем самые узкие сиденья. Второй пассажир (интроверт) выберет ряд номер \(1\), так как это единственный оставшийся пустой ряд. Третий пассажир (экстраверт) выберет ряд номер \(1\), так как в нем уже сидит один пассажир и этот ряд самый широкий. Четвертый пассажир (экстраверт) выберет ряд номер \(2\), так как это единственный ряд, в котором осталось свободное место.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 1
0011
|
2 1 1 2
|
|
2
|
6
10 8 9 11 13 5
010010011101
|
6 6 2 3 3 1 4 4 1 2 5 5
|