Тур II, задача 2

Байтлэнд славится своей нестандартной организацией системы железнодорожного сообщения. Каждый город имеет свою собственную железнодорожную станцию. Если поезд проходит через некоторый город X, то все пассажиры, которые приобрели билеты на этот поезд, не рассаживаются по свободным местам проходящего состава, а специально для них в начало или конец состава прицепляют дополнительный вагон. Даже если не было продано ни одного билета, вагон всегда прицепляют. Из первого города поезд всегда отправляется с одним вагоном. В последнем городе вагон не прицепляется.

Совсем недавно в целях оптимизации работы с пассажирами было принято решение о том, что начальник поезда должен всегда располагаться в середине поезда – это позволит сократить время поиска начальника поезда пассажирами. То есть, если в поезде K вагонов, то серединой поезда или средним вагоном будем называть вагон с порядковым номером (целая часть деления числа K + 1 на 2). Будем считать, что вагоны нумеруются последовательно от начала состава начиная с единицы. Также следует отметить, что кроме порядкового номера каждый вагон имеет свой уникальный и никогда не изменяющийся номер.

Но так как состав проходит через множество промежуточных городов и вагоны постоянно прицепляются то в начало, то в конец состава, место расположения начальника поезда может меняться и установить вагон, в котором на данный момент находится начальник поезда, не так просто.

Рисунок №1: 4 города. Символ “F” – добавление вагона в начало состава, символ “L” – в конец состава. Вертикальными стрелками показан вагон, в котором располагается начальник поезда.

Для приведенного выше примера поезд проходит через 4 города A, B, C, D в соответствующем порядке. С первой станции A поезд отправляется с одним вагоном, уникальный номер которого равен 2. Так как вагон всего один, то начальник находится именно в нем. Далее, на второй станции B, в начало состава добавляется вагон с уникальным номером 3. Так как , то начальник поезда находится в вагоне с порядковым номером 1 и уникальным номером 3. Далее, на третьей станции C в конец состава был добавлен вагон с уникальным номером 6, после чего начальник поезда снова находится в вагоне с порядковым номером 2 и уникальным номером 2. На станции D, так как она конечная, вагон не прицепляется.

Вам задается общее количество городов, через которые следует поезд, а также для каждого города, кроме последнего, предоставляется информация о прицепном вагоне – это уникальный номер вагона и место присоединения к составу: либо в начало, либо в конец состава. Ваша задача – для каждого города, через который проходит поезд (кроме последнего), определить уникальный номер вагона, в котором находится начальник поезда после проезда через соответствующую станцию.