题意：

在一个由男生和女生组成的队中，每一秒如果一个男生在一个女生的前面，

他们就会互换位置。求女生全换到最前面用的最少时间。

ＤＰ转移方程：　ans=max(ans+１,pre)；　pre是从后往前到当前位置时的女生数

　　　　　　　　意思是在当前如果是男生并且该　男生后面有女生的存在，则选取

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>

using namespace std;  



int main()
{
	freopen("in.txt","r",stdin);
	int i,j,k;
	string s;
	cin>>s;
	
	int ans=0;
	int pre=0;
	for (i=s.size()-1;i>=0;i--)
	{
		if (s[i]=='F')
			pre++;
		else  if (pre)
			ans=max(ans+1,pre);
	}
	
	cout<<ans<<endl;
	
	
	return 0;
}

D. Queue

time limit per test

memory limit per test

input

output

n

i-th position has a boy and the (i + 1)-th position has a girl, then in a second, the i-th position will have a girl and the (i + 1)-th one will have a boy.

Let's take an example of a line of four people: a boy, a boy, a girl, a girl (from the beginning to the end of the line). Next second the line will look like that: a boy, a girl, a boy, a girl. Next second it will be a girl, a boy, a girl, a boy. Next second it will be a girl, a girl, a boy, a boy. The line won't change any more.

Your task is: given the arrangement of the children in the line to determine the time needed to move all girls in front of boys (in the example above it takes 3 seconds). Baking buns takes a lot of time, so no one leaves the line until the line stops changing.

Input

s1s2... sn (1 ≤ n ≤ 106), consisting of capital English letters M and F. If lettersi equals M, that means that initially, the line had a boy on the i-th position. If letter si equals F, then initially the line had a girl on the i-th position.

Output

0.

Sample test(s)

input

MFM

output

1

input

MMFF

output

3

input

FFMMM

output

0

Note

MFM  →  FMM.

MMFF  →  MFMF  →  FMFM  → FFMM.