Circle Cross Stamps

Interview

Time limit2sMemory limit512 MB

Summary

Given a row of O and X marks printed by single circles, single crosses, and two-mark circle-cross stamps in either orientation, find the largest possible count of circle-cross stamps.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, String
Solved: No attempts yet

Problem

JOI has at least 0 of each of three kinds of stamps: circle stamps, cross stamps, and circle cross stamps. These stamps can print circle and cross marks 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 in a horizontal line, and by changing the orientation of the stamp, it can print either a cross to the right of a circle or a circle to the right of a cross.

JOI used each of the stamps he has exactly once, in some order, to print circles and crosses in a horizontal line on paper. The row of printed circles and crosses is represented by the string S. S is a string of length N consisting of O and X, where S_i = O means that the i-th mark from the left that JOI printed is a circle, and S_i = X means that it is a cross (1 ≤ i ≤ N).

You do not know how many stamps JOI has, but you know the row of circles and crosses that JOI printed. From the printed row of circles and crosses, find the maximum possible number of circle cross stamps that JOI has.

Input

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

N
S

Output

Output the maximum possible number of circle cross stamps that JOI has.

Constraints

1 ≤ N ≤ 100000 (= 10^5)
S is a string of length N.
Each character of S is O or X.

Examples3

Example 1
Input
```
5
OXXOX
```
Expected output
```
2
```
Example 2
Input
```
14
OXOXOXOXXOXOXO
```
Expected output
```
7
```
Example 3
Input
```
10
OOOOOOOOOO
```
Expected output
```
0
```