В школьной столовой собралась очередь за булочками, состоящая из n человек — мальчиков и девочек. В то время, пока булочки еще готовятся, в очереди происходят некоторые изменения. Каждую секунду все мальчики, которые стоят непосредственно перед девочками, одновременно пропускают их вперед. Другими словами, если в какой-то момент времени i-ым в очереди стоит мальчик, а (i + 1)-ой — девочка, то через секунду на i-ом месте будет стоять девочка, а на (i + 1)-ом — мальчик.
Рассмотрим пример очереди, в которой стоят четыре человека: мальчик, мальчик, девочка, девочка (перечислены от начала очереди). Тогда через одну секунду очередь будет выглядеть так: мальчик, девочка, мальчик, девочка. Через две — девочка, мальчик, девочка, мальчик. Через три — девочка, девочка, мальчик, мальчик. Далее очередь меняться не будет.
Вам требуется по заданной расстановке ребят в очереди определить, через какое время все девочки окажутся впереди мальчиков (в рассмотренном выше примере это время равно 3-ем секундам). Булочки готовятся чрезвычайно долго, поэтому никто не успевает покинуть очередь до того момента, как в ней перестанут происходить изменения.
Выходные данные
Выведите единственное целое число — количество секунд, через которое все девочки в очереди окажутся перед мальчиками. Если в очереди все ребята одного пола, выведите 0.
Примечание
В первом тестовом примере последовательность изменений выглядит следующим образом: MFM → FMM.
Второй тестовый пример соответствует примеру из условия. Последовательность изменений: MMFF → MFMF → FMFM → FFMM.