D. Дараалал (очер)

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ ширхэг сургуулийн сурагчид сургуулийнхаа цайны газар жагсан зогсчээ. Үзэмтэй талх хараахан бэлэн болоогүй байсан ба дараалалд өөрчлөлт орж байв.

Секунд тутамд охидын эгц урд зогсож хөвгүүд охидтойгоо байраа сольж байлаа. (охид нь дарааллын эхэн рүү ойртоно.) Өөрөөр хэлбэл $i$ дэх байрлал дээр хүү, $(i+1)$ байрлал дээр охин байвал тэд байраа сольж $i $ дэх байран дээр охин ирж, $(i+1)$ дээр хүү очно.

Дараах байралалаар жишээ авъя: хүү, хүү, охин, охин (дарааллын эхнээс). Дараагийн секундэд байрлал: хүү, охин, хүү, охин. Дараагийн секундэд байрлал: охин, хүү, охин, хүү. Дараагийн секундэд байрлал: охин, охин, хүү, хүү болно.

Таны даалгавар бол бүх охид бүх хөвгүүдийнхээ өмнө гарахад хэдэн секунд шаардлагатайг тооцоолох юм. (Дээд жишээн дээр 3 секунд). Үзэмтэй талх хийх нь нэлээн хугацаа шаарддаг учраас дараалал өөрчлөгдөж дуусахаас урьд хэн ч орхиж явахгүй.

Оролт

Эхний мөрөнд том M, F үсгүүдээс тогтох $s_1s_2... s_n$ $(1\le n\le 10^6)$ үсгүүдийн дараалал өгөгдөнө. $s_i$ нь M бол анх $i$ дэх байрлал дээр хүү байсныг илтгэнэ. Харин $s_i$ нь F бол анх $i$ дэх байрлал дээр охин байсныг илтгэнэ.

Гаралт

Бүх охид бүх хөвгүүдийн өмнө гарахад шаардах хугацааний(секундээр) тоон утгыг хэвлэнэ үү. Дараалалд дан охид, эсвэл хөвгүүд зогсож байсан бол 0 гэж хэвлэнэ үү.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
MFM
Гаралт
1
Оролт
MMFF
Гаралт
3
Оролт
FFMMM
Гаралт
0

Тэмдэглэл

In the first test case the sequence of changes looks as follows: MFM$ $ -> $ FMM$.

The second test sample corresponds to the sample from the statement. The sequence of changes is: MMFF$ $ -> $ MFMF$ $ -> $ FMFM$ $ -> $ FFMM$.

Сэтгэгдлүүдийг ачааллаж байна...