JOI có ba loại con dấu: con dấu tròn, con dấu chéo và con dấu tròn-chéo. Với mỗi loại, cậu có thể có từ \(0\) con dấu trở lên. Các con dấu này dùng để in dấu tròn hoặc dấu chéo lên giấy.

Một con dấu tròn in ra một dấu tròn; một con dấu chéo in ra một dấu chéo. Một con dấu tròn-chéo in ra một dấu tròn và một dấu chéo nằm cạnh nhau trên một hàng ngang. Bằng cách xoay con dấu, có thể in dấu chéo ở bên phải dấu tròn hoặc in dấu tròn ở bên phải dấu chéo.

JOI đã dùng mỗi con dấu mình có đúng một lần, theo một thứ tự thích hợp, để in thành một hàng gồm các dấu tròn và dấu chéo. Hàng dấu đã in được biểu diễn bởi chuỗi \(S\) có độ dài \(N\), chỉ gồm hai ký tự O và X. Với \(1 \le i \le N\), ký tự \(S_i\) là O nếu dấu thứ \(i\) từ trái sang là dấu tròn, và là X nếu đó là dấu chéo.

Bạn không biết JOI có bao nhiêu con dấu mỗi loại, nhưng biết hàng dấu mà cậu đã in. Hãy tìm số con dấu tròn-chéo lớn nhất mà JOI có thể đã có.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N
S

Dữ liệu ra

In ra số con dấu tròn-chéo lớn nhất mà JOI có thể đã có.

Ràng buộc

• \(N\) là số nguyên, \(1 \le N \le 10^5\).
• \(S\) có độ dài \(N\).
• Mỗi ký tự của \(S\) là O hoặc X.

Ví dụ

5
OXXOX

2

14
OXOXOXOXXOXOXO

7

10
OOOOOOOOOO

0

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.