Problem Description

JOI has three types of stamps: circle stamps, cross stamps, and circle-cross stamps, each of which he has zero or more. These stamps can print circles and crosses on paper.

Using a circle stamp prints one circle, and using a cross stamp prints one cross. Using a circle-cross stamp prints one circle and one cross side by side. The orientation of the stamp can be changed so that the circle can be to the right of the cross or the cross can be to the right of the circle.

JOI used each of his stamps exactly once in some order to print circles and crosses in a row on paper. The printed sequence of circles and crosses is represented by a string \( S \). \( S \) is a string of length \( N \) composed of 'O' and 'X', where \( S_i = \) 'O' indicates that the \( i \)-th mark from the left printed by JOI is a circle, and \( S_i = \) 'X' indicates that it is a cross (\( 1 \leq i \leq N \)).

You do not know the number of stamps JOI has, but you know the sequence of circles and crosses he printed. Determine the maximum possible number of circle-cross stamps JOI could have based on the printed sequence of circles and crosses.

Input Format

The input is given from the standard input in the following format:

\( N \) \( S \)

Output Format

Output the maximum possible number of circle-cross stamps JOI could have.

Sample Input and Output

Sample Input #1

5
OXXOX

Sample Output #1

2

Sample Input #2

14
OXOXOXOXXOXOXO

Sample Output #2

7

Sample Input #3

10
OOOOOOOOOO

Sample Output #3

0

Notes/Hints

Constraints

• \( 1 \leq N \leq 100000 \) (\( = 10^5 \))
• \( S \) is a string of length \( N \).
• Each character in \( S \) is either 'O' or 'X'.

Sample Explanation 1

The marks printed by JOI are, from left to right, circle, cross, cross, circle, cross. If JOI has 0 circle stamps, 1 cross stamp, and 2 circle-cross stamps, he can print the marks in the following order:
- Use the first circle-cross stamp to print circle and cross in this order.
- To the right of this, use the second circle-cross stamp to print cross and circle in this order.
- Finally, to the right of this, use the cross stamp to print a cross.
Since it is not possible to have 3 or more circle-cross stamps, output 2.

见题面 Input 部分

见题面 Output 部分