Minimal Doors to Connect Farm Regions

Farmer John has built a peculiar fence on his farm. Starting at the origin ((0,0)), he takes (N) steps. Each step is exactly 1 unit in one of the four cardinal directions: North, South, East, or West. For every move, he constructs a unit-length segment of fence along his path. Note that he may visit the same point or construct the same segment several times, and the fence may even cross itself. As a result, the fence partitions the plane into several regions (one of which is the unbounded exterior region).

A door can be installed on any of the unit-length fence segments (i.e. on any step that has been taken) and will connect the two regions on either side of that segment. Farmer John wants to install the minimum number of doors such that every region becomes accessible from every other region. It can be shown that the minimum number of doors required is given by

[ \text{Doors} = E - V + 1 ]

where (E) is the number of distinct fence segments (edges) built, and (V) is the number of distinct points (vertices) visited during the walk.

For example, if (N = 4) and the path is N E S W (i.e. forming a square), then (V = 4) and (E = 4), so the answer is (4 - 4 + 1 = 1).

inputFormat

The first line contains an integer (N) (the number of steps). The second line contains a string of length (N) consisting only of the characters 'N', 'S', 'E', and 'W', indicating the direction of each step.

outputFormat

Output a single integer, the minimum number of doors that must be installed so that any region can be reached from any other region.

sample

4
NESW

1