AiGo

Interview

Time limit2sMemory limit512 MB

Summary

Given a 1D Go board, find the most black stones white can capture with one legal move, where white may not place a stone that forms an enclosed white chain.

Level: Easy3 of 10
Topics: Brute force, Simulation, String
Solved: No attempts yet

Problem

Recently, AIs that play Go have been studied extensively. Your friend Hikaru plans to develop a new Go AI named Sai and pitch it to company F or company G. As a first step, Hikaru will build an AI for 1D-Go, a restricted version of Go.

In both Go and 1D-Go, capturing stones is an important strategy. Hikaru asks you to implement one of the capturing functions.

In 1D-Go, the board consists of $L$ grids in a row. A state of the board is a string $S$ of length $L$ . The $i$ -th character describes the $i$ -th grid:

'B' means the grid holds a black stone.
'W' means the grid holds a white stone.
'.' means the grid is empty.

A maximal run of consecutive stones of the same color is called a chain. When a chain is surrounded by stones of the opponent's color, the chain is captured. More precisely, if the $i$ -th and $j$ -th grids ( $1 < i+1 < j \le L$ ) contain white stones and every grid $k$ with $i < k < j$ contains a black stone, those black stones are captured. The same holds with the colors swapped.

The next move belongs to the player with white stones. The player can place a white stone on an empty cell. However, the player cannot create a chain of white stones that is surrounded by black stones, even if the same move captures some black stones. The given state has at least one empty grid where white can play, and no chain is already surrounded.

Write a program that computes the maximum number of black stones that can be captured by the next move of the white player.

Input

The input is a single line containing the integer $L$ ( $1 \le L \le 100$ ) and the string $S$ with $|S| = L$ , separated by a space.

Output

Output the maximum number of black stones that can be captured by the next move, on a single line.

Hint

In the 3rd and 4th test cases, the player cannot place a white stone on the 4th grid, because the white chain would be surrounded by black stones. This differs from the original Go.

In the 5th test case, the player cannot capture any black stones even if a white stone is placed on the 4th grid. Black stones cannot be captured by enclosing them with the board edge and a white stone. This rule also differs from the original Go.

Examples5

Example 1
Input
```
5 .WB..
```
Expected output
```
1
```
Example 2
Input
```
5 .WBB.
```
Expected output
```
2
```
Example 3
Input
```
6 .WB.B.
```
Expected output
```
0
```
Example 4
Input
```
6 .WB.WB
```
Expected output
```
0
```
Example 5
Input
```
5 BBB..
```
Expected output
```
0
```