Problem E
Rotating Mugs

You have $M$ mugs, indexed from $0$ to $M-1$, in front of you, and your task is to rotate the mugs so that the North side faces you. However, you may perform only magical rotations. A magical rotation consists of the following three steps:

1. Choose integers $a$ and $b$ such that $0 \le a < M$, $0 \le b < M-1$, and $a \neq b$. Note that $b$ cannot be the last index.

2. Swap the mugs at indices $a$ and $b$ without rotating them.

3. Take the mug now at index $b$ (the one moved from index $a$) and its neighbor to the right, then rotate both by $90^\circ $.

Note that a magical rotation has to contain all three steps, including swapping the mugs as well as rotating them afterwards.

When rotating a mug by $90^\circ $:

• A mug with its North side facing you will now have its West side facing you.

• A mug with its West side facing you will now have its South side facing you.

• A mug with its South side facing you will now have its East side facing you.

• A mug with its East side facing you will now have its North side facing you.

You now wonder whether it is possible to arrange all the mugs so that their North sides face you using only magical rotations. To impress the task assigner, you would like to minimize the number of magical rotations.

If you do not have enough mugs on hand to experiment, you can use this website, created using Lovable, to simulate the magical rotations.

Input

The first line contains an integer $M$ ($2 \leq M \leq 5 \cdot 10^5$), the number of cups infront of you.

The second line contains a string of $M$ characters $c_1, c_2, \dots , c_M$, where $c_i$ is one of the four characters ‘N’, ‘W’, ‘S’, ‘E’, denoting the side of the $i$-th mug currently facing you.

Output

Print an integer: the minimum number of magical rotations required to make all mugs face the North side toward you. If it is impossible, print -1.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of samples

In the first smaple, we start out with two mugs with initial state WW. By repeatedly choosing $a = 1$ and $b = 0$, the mugs will switch places and rotate $90^\circ $. Doing this 3 times, turns the mugs into the desired state. There exist no sequence of magical rotations that can achieve this in fewer than 3 moves.

Figure 1: Sequence of 3 magical rotations for sample 1.

In the second sample, we start out with the mugs in the state ESE. We do the following two magical rotations:

• Choosing $a = 2$, $b = 1$ will first switch the positions of the mugs, leading to EES. Then we rotate the mugs now at position $b = 1$, and the one to the right of it by $90^\circ $, resulting in ENE.

• Choosing $a = 0$, $b = 1$ will first switch the labels to NEE. Rotating the mug now at $b = 1$ and the one to the right of it results in NNN.

There exist no sequence of magical rotations that can achieve this in fewer than 2 moves.

Figure 2: Sequence of 2 magical rotations for sample 2.

In the third sample, it can be proven that there exist no sequence of magical rotations that can turn all mugs such the mugs become NNNNNN.

2
WW

3

3
ESE

2

6
NESWSE

-1