← 返回题目列表

Codeforces · 353/D

D. 队列

中文机器翻译题面 查看原题

学校食堂的包子摊前有n个小学生,男生女生,排着队。面包还没有准备好,生产线正在发生一些变化。

每一秒,所有站在女孩面前的男孩都会同时与女孩交换位置(这样女孩就可以更接近队伍的开头)。换句话说,如果在某个时刻第i个位置是男孩,第(i+1)个位置是女孩,那么在一秒钟内,第i个位置将是女孩,第(i+1)个位置将是男孩。

我们以四个人的队伍为例:一个男孩,一个男孩,一个女孩,一个女孩(从队伍的开始到结束)。下一秒,这条线将如下所示:一个男孩,一个女孩,一个男孩,一个女孩。下一秒就会是女孩,男孩,女孩,男孩。下一秒就会是女孩,女孩,男孩,男孩。线路不会再变了。

你的任务是:根据孩子们在队列中的排列情况,确定将所有女孩移到男孩前面所需的时间(在上面的示例中需要 3 秒)。烤面包需要很长时间,所以直到队伍停止换线之前都没有人离开队伍。

输入

第一行包含不带空格的字母序列 s1s2...sn (1 ≤ n ≤ 106),由大写英文字母 M 和 F 组成。如果字母 si 等于 M,则表示最初该行第 i 个位置上有一个男孩。如果字母 si 等于 F,则最初该行的第 i 个位置上有一个女孩。

输出

打印一个整数 - 将队列中的所有女孩移动到男孩前面所需的秒数。如果该行只有男孩或只有女孩,则打印 0。

示例

输入 #1

MFM

输出 #1

1

输入 #2

MMFF

输出 #2

3

输入 #3

FFMMM

输出 #3

0

注意

在第一个测试用例中,更改顺序如下:MFM → FMM。

第二个测试样本对应于声明中的样本。变化顺序为:MMFF→MFMF→FMFM→FFMM。