Please Take My Gift 2

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.

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.

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