Cho một xâu kí tự ~S~ chỉ gồm các kí tự thuộc tập {T, R, M}. Ta được phép thực hiện thao tác sau một số lần, có thể không thực hiện lần nào: chọn hai vị trí phân biệt ~x, y~ ~(1 \le x, y \le |S|)~, rồi hoán đổi hai kí tự ở hai vị trí này cho nhau.

Một xâu được gọi là hợp lệ nếu các kí tự giống nhau luôn nằm liên tiếp nhau. Nói cách khác, mỗi loại kí tự xuất hiện trong nhiều nhất một đoạn liên tục duy nhất trên xâu.

Yêu cầu: Tính số thao tác hoán đổi ít nhất cần thực hiện để biến xâu ~S~ thành một xâu hợp lệ.

Input

• Dòng đầu tiên chứa ~n~, là độ dài xâu kí tự ~(1 \le n \le 5 \cdot 10^5)~.

• Dòng thứ hai chứa xâu kí tự ~S~ chỉ gồm các kí tự thuộc tập {T, R, M}.

Output

Một số nguyên duy nhất là số thao tác hoán đổi ít nhất cần thực hiện.

Scoring

Sample Input 1

6
TRTTMM

Sample Output 1

1

Sample Input 2

4
TTRR

Sample Output 2

0

Notes

Hoán đổi vị trí ~2~ và ~4~ được TTTRMM.

Xâu ban đầu trong ví dụ thứ hai đã hợp lệ.