Sawmills

Time limit1sMemory limit128 MB

Summary

Given a string of g and t points along a line, pair every g with a distinct t using non-crossing north-side arcs so the summed distance is minimal, or report NIE.

Level: Medium5 of 10
Topics: Greedy, Stack, Math, Implementation
Solved: No attempts yet

Problem

All the farms in the village of Byteram lie on the same side of a very long road, because the Byteland National Park occupies the other side. To grow the local economy, the mayor decided to move the village into the furniture business.

The village has exactly as many sawmills as farms, and all of them stand along the single road. Each sawmill supplies wood to exactly one farm and each farm receives wood from exactly one sawmill, so the sawmills and farms form a one-to-one matching.

Wood travels along short access roads that each connect one sawmill to one farm. Because the national park lies to the south, every access road is built on the north side of the main road, and no two access roads may cross.

Label the points along the road $1, 2, \dots, 2n$ from west to east. The length of an access road that joins the points at positions $p$ and $q$ is $|p - q|$ . Among all valid non-crossing assignments, find the smallest possible total length of all access roads.

Input

The first line contains one integer $n$ ( $1 \le n \le 1{,}000{,}000$ ), the number of farms.

The second line contains one string of length $2n$ built only from the letters g and t, listing the points from west to east. The letter g marks a farm (gospodarstwo is Polish for farm) and the letter t marks a sawmill (tartak is Polish for sawmill). The Byteland National Park lies to the south of the road.

Output

A valid assignment connects every farm to exactly one distinct sawmill with access roads that all run on the north side and never cross one another.

If no valid assignment exists, print a single line containing the word NIE (Polish for no).

Otherwise print a single integer: the minimum possible total length of all access roads over every valid non-crossing assignment, where the length of a road joining positions $p$ and $q$ is $|p - q|$ .

Hint

A sample layout of sawmills (white circles) and farms (black circles).

Note: the gaps drawn between the farms, the sawmills, and the main road are only there to make the picture clearer. In reality the sawmills and farms sit right next to the road, and no access road can be built between a sawmill or farm and the main road.

Examples3

Example 1
Input
```
3
gtggtt
```
Expected output
```
5
```
Example 2
Input
```
1
gt
```
Expected output
```
1
```
Example 3
Input
```
2
gtgt
```
Expected output
```
2
```