[USACO16Jan]建门 gates

题目描述

Farmer John 打算在他农场的一部分,建设一个围栏。但是因为没有认真做事,建造完成后,围栏变成一个很奇怪的形状。 具体来说,FJ从(0,0)出发,走了N 步,每步移动一单位(向东、向南、向西或向东)。 他走过的每一步,都会留下一段单位长度的围栏。例如,如果他的第一步向北,他建造一单位从(0,0)到(0,1)的围栏。 FJ可能重复到达点多次,他也可能重复建造一段围栏多次。如果他的路径穿过一段已经建成的围栏,他的围栏也有可能会有交叉。 不用说,FJ看到完成的围栏时,一定很沮丧。特别的,他发现一些区域被围栏封闭起来,从而无法到达。FJ想在围栏上,安装一些门来解决这个问题。 门可以安装在任意一段单位长度(注:必须是之前走过的某一步)的围栏上,从而可以穿越这段围栏的两侧。 请计算FJ最少需要安装多少个门,才能保证农场上任意区域到任意区域都可到达。

输入输出格式

输入格式


1行:包含N。 2行:包含一个长度为N的字符串,描述FJ的路径。每个字符为N(北),E(东),S(南),或W(西)。

输出格式


输出一个整数,表示为了保证农场所有区域的连通性,FJ最少需要安装多少个门。

输入输出样例

输入样例 #1

14
NNNESWWWSSEEEE

输出样例 #1

2

说明

注意,如果农场初始连通,答案就是0。 [数据范围] n<=1000