내 선물을 받아줘 2

욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물을 전달하려고 한다. 며칠 동안 관찰한 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.

구사과가 있는 곳은 $1 \times N$ 크기의 직사각형 지도로 나타낼 수 있으며 $1 \times 1$ 크기의 정사각형 칸 $N$개로 나뉜다. 구사과의 위치는 $(1, x)$로 나타내며 왼쪽에서 $x$번째 칸을 뜻한다.

각 칸에는 E와 W 중 한 문자가 쓰여 있다. 구사과가 $(1, x)$에 있을 때 서 있는 칸의 문자가 E이면 $(1, x+1)$로, W이면 $(1, x-1)$로 순간이동한다. 구사과는 지치지 않으므로 이동을 계속한다.

욱제는 구사과의 시작 위치를 모른다. 시작 위치와 관계없이 구사과가 이동 중에 선물을 가져가도록 칸 위에 선물을 놓으려고 한다. 선물이 놓인 칸에 구사과가 들어서면 구사과는 선물을 가져간다. 구사과가 어디에서 시작하더라도 선물을 가져가게 되는 선물의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 지도의 길이 $N$이 주어진다. ($2 \le N \le 1{,}000$)

둘째 줄에 길이가 $N$인 지도가 주어진다. 지도는 E와 W로 이루어진 길이 $N$인 문자열이다.

지도에 쓰여 있는 대로 이동했을 때 지도를 벗어나는 경우는 없다.

첫째 줄에 선물을 놓아야 하는 칸 개수의 최솟값을 출력한다.