CF353D Queue

有 $n$ 个学生（男孩和女孩）在学校食堂的包子摊前排队。包子还没做好，这条队伍正在发生一些变化。 每一秒，所有站在女孩前面的男孩会同时与身后的女孩交换位置（让女孩能更靠近队伍的开头）。换句话说，如果在某一时刻，第 $i$ 个位置是男孩，第 $i+1$ 个位置是女孩，那么一秒后，第 $i$ 个位置就会是女孩，第 $i+1$ 个位置则会是男孩。 例如，假如有四个人排成一列：男孩、男孩、女孩、女孩（从队头到队尾）。下一秒队伍变为：男孩、女孩、男孩、女孩。再下一秒变为：女孩、男孩、女孩、男孩。再下一秒变为：女孩、女孩、男孩、男孩。从此以后队伍不会再发生变化。 你的任务是：给定队伍中学生的初始排列，判断需要多少秒，使得所有女孩都排到所有男孩的前面（在上述例子中需要 3 秒）。因为做包子很慢，所以在队伍停止变化之前没人离开。

第一行为一个没有空格的字母序列 $s_{1}s_{2}…s_{n}$ $ (1\leq n\leq 10^{6}) $，只包含大写英文字母 M 和 F。如果字母 $s_{i}$ 是 M，表示第 $i$ 个位置最开始是一个男孩；如果 $s_{i}$ 是 F，表示第 $i$ 个位置最开始是一个女孩。

输出一个整数，表示需要多少秒才能让队伍中的所有女孩都排在所有男孩前面。如果队伍中只有男孩或只有女孩，输出 $0$。

第一个样例的变化过程如下：MFM $\rightarrow$ FMM。 第二个样例对应题目描述中的示例。变化过程为：MMFF $\rightarrow$ MFMF $\rightarrow$ FMFM $\rightarrow$ FFMM。 由 ChatGPT 5 翻译