Liars

Interview

Time limit2sMemory limit512 MB

Summary

Given a circular string of answers about whether the right neighbor is a liar, find the minimum number of liars consistent with all answers, or -1.

Level: Medium4 of 10
Topics: Brute force, Implementation, Array
Solved: No attempts yet

Problem

$N$ people at an algorithm camp gather at the front of the classroom and sit in a circle. They are numbered $0$ through $N-1$ counterclockwise.

Every participant is either honest or a liar. An honest person always tells the truth, and a liar always tells a lie.

The host asked each person whether the person sitting to their right is a liar. An honest person answers truthfully and a liar answers falsely. Both an honest person and a liar may refuse to answer.

Given the answers, write a program that prints the smallest possible number of liars if some assignment of honest people and liars produces exactly those answers, and $-1$ if no assignment does.

Input

The first line contains the number of people $N$ . ( $2 \le N \le 50$ )

The second line contains the answers as a string of length $N$ . The $i$ -th character from the left, counting from $0$ , is the answer of person $i$ .

An answer of L means the person said the one to their right is a liar, H means the person said that one is honest, and ? means the person refused to answer.

Output

If some assignment of honest people and liars produces the given answers, print the smallest possible number of liars. Otherwise print $-1$ .

Note

The numbering runs counterclockwise, so the person sitting to the right of person $i$ is person $(i+1) \bmod N$ .

Examples5

Example 1
Input
```
3
LLH
```
Expected output
```
1
```
Example 2
Input
```
5
?????
```
Expected output
```
0
```
Example 3
Input
```
5
LHLH?
```
Expected output
```
2
```
Example 4
Input
```
10
??LLLLLL??
```
Expected output
```
3
```
Example 5
Input
```
3
LLL
```
Expected output
```
-1
```