В школьной столовой собралась очередь за булочками, состоящая из n человек — мальчиков и девочек. В то время, пока булочки еще готовятся, в очереди происходят некоторые изменения. Каждую секунду все мальчики, которые стоят непосредственно перед девочками, одновременно пропускают их вперед. Другими словами, если в какой-то момент времени i-ым в очереди стоит мальчик, а (i + 1)-ой — девочка, то через секунду на i-ом месте будет стоять девочка, а на (i + 1)-ом — мальчик.

Рассмотрим пример очереди, в которой стоят четыре человека: мальчик, мальчик, девочка, девочка (перечислены от начала очереди). Тогда через одну секунду очередь будет выглядеть так: мальчик, девочка, мальчик, девочка. Через две — девочка, мальчик, девочка, мальчик. Через три — девочка, девочка, мальчик, мальчик. Далее очередь меняться не будет.

Вам требуется по заданной расстановке ребят в очереди определить, через какое время все девочки окажутся впереди мальчиков (в рассмотренном выше примере это время равно 3-ем секундам). Булочки готовятся чрезвычайно долго, поэтому никто не успевает покинуть очередь до того момента, как в ней перестанут происходить изменения.