Zvimbalius

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string of N moves in four directions, find the fewest moves to change so the drone ends at its starting point, or report NEGALIMA.

Level: Easy3 of 10
Topics: String, Math
Solved: No attempts yet

Problem

Vytis has a new toy: a remote-controlled unmanned aerial vehicle, also called a drone or zvimbalius. The drone is an unmanned helicopter that flies according to the commands it receives.

Vytis's drone understands four commands, S, P, R, and V. They tell the drone to fly one meter north, south, east, or west, respectively.

Vytis tested the toy by entering N commands. After entering them, he realized the drone might not return to its starting point after executing all of them. Fixing the commands is hard. The drone software does not allow adding or deleting commands that were already entered, and a command can only be changed one at a time. Vytis wants to change as few commands as possible so that the drone returns to its starting point after executing all of them.

Find the minimum number of commands Vytis needs to change so that the drone returns to its starting point.

Input

The first line contains the number of commands N. The second line contains a string of N commands k1k2...kN with no spaces, where ki is the i-th command, encoded as described above.

Output

Print one integer: the minimum number of commands that must be changed so that the drone returns to its starting point.

If it is impossible to change the commands so that the drone returns to its starting point, print NEGALIMA.

Constraints

1 ≤ N ≤ 100 000

Examples2

Example 1
Input
```
4
SSRR
```
Expected output
```
2
```
Example 2
Input
```
3
PRV
```
Expected output
```
NEGALIMA
```