Hàng Chờ Mua Bánh

Có $n$ học sinh xếp thành một hàng chờ mua bánh. Mỗi học sinh là nam (kí hiệu M) hoặc nữ (kí hiệu F).

Mỗi giây, đồng thời tại mọi vị trí $i$ mà học sinh vị trí $i$ là M và học sinh vị trí $i+1$ là F, hai học sinh này đổi chỗ cho nhau (nữ tiến lên một bước, nam lùi xuống một bước).

Việc đổi chỗ diễn ra song song trên cả hàng: quyết định vị trí nào đổi được xét theo cấu hình trước khi giây đó bắt đầu, không phải sau khi vài cặp đã đổi.

Yêu cầu: cho cấu hình ban đầu, tính số giây cần thiết để hàng chuyển thành trạng thái mà tất cả nữ đứng trước tất cả nam (nghĩa là không còn bất kì cặp M đứng ngay trước F nào). Nếu hàng ban đầu đã ở trạng thái này (kể cả trường hợp chỉ có nam hoặc chỉ có nữ), in ra $0$.

Dữ liệu vào

Một dòng chứa xâu $s=s_1{s}_2\dots s_n$ gồm các kí tự in hoa M và F. Kí tự $s_i$ mô tả học sinh tại vị trí $i$ trong hàng.

Dữ liệu ra

In ra một số nguyên duy nhất — số giây cần thiết để toàn bộ nữ đứng trước toàn bộ nam.

Ràng buộc

• $1\le n\le {10}^6$
• $s_i\in \{\text{M},\text{F}\}$

Ví dụ