Card Control

Interview

Time limit1sMemory limit1024 MB

Summary

Given a deck of N O cards and N X cards, find the fewest times you must move a chosen card to the top so that Junseok, who takes cards 1, 3, 5, ..., wins.

Level: Medium4 of 10
Topics: Brute force, Greedy, Simulation
Solved: No attempts yet

Problem

Junseok and Suhyeon are playing a card game. There are $N$ cards marked O and $N$ cards marked X, all shuffled together. The game proceeds as follows.

Junseok takes the topmost card.
Suhyeon takes the next card.
If Junseok's card and Suhyeon's card are the same, the round is a tie. If they differ, the player holding the card marked O gains $1$ point.

The player with the higher score at the end wins.

Junseok can manipulate the cards before the game starts. Specifically, in one manipulation he can take out any one card he wants and place it on top of the deck.

Given that Junseok knows the initial arrangement, how many manipulations are needed for him to win with as few manipulations as possible?

Input

The first line gives $N$ . ( $1 \leq N \leq 5$ )

The next line gives the symbols written on the cards, starting from the topmost card.

Output

Print the minimum number of card manipulations.

Examples1

Example 1
Input
```
2
X O O X
```
Expected output
```
1
```