Please Take My Gift 2

Interview

Time limit2sMemory limit256 MB

Summary

Given a 1 by N arrow map where every walk stays inside, place the fewest gifts so that a walk from any starting cell hits a gift.

Level: Medium7 of 10
Topics: Graph, Greedy, Implementation, DFS
Solved: No attempts yet

Problem

Ukje is an avid fan of Gusagwa. Today Ukje wants to hand a gift to Gusagwa. After watching for several days, Ukje has learned the complete movement pattern of Gusagwa.

The place where Gusagwa stays is a rectangular map of size $1 \times N$ , divided into $N$ square cells of size $1 \times 1$ . The position of Gusagwa is written as $(1, x)$ , which means the $x$ th cell from the left.

Each cell holds either E or W. When Gusagwa is at $(1, x)$ , Gusagwa teleports to $(1, x+1)$ if the cell shows E and to $(1, x-1)$ if it shows W. Gusagwa never gets tired and keeps moving.

Ukje does not know the starting position of Gusagwa. Ukje wants to place gifts on cells so that Gusagwa picks up a gift during the walk no matter where the walk starts. When Gusagwa enters a cell with a gift, Gusagwa always picks it up. Write a program that finds the smallest number of cells that guarantees this.

Input

The first line has the length $N$ of the map. ( $2 \le N \le 1{,}000$ )

The second line has the map as a string of length $N$ . The string consists only of E and W.

A walk that follows the map never leaves the map.

Output

Print the smallest number of cells that need gifts on the first line.

Examples2

Example 1
Input
```
6
EEWWEW
```
Expected output
```
2
```
Example 2
Input
```
5
EEEEW
```
Expected output
```
1
```