Mixed Messages

Time limit2sMemory limit2048 MB

Summary

Given a string that interleaves several messages, one of which is the word spbsu, find the minimum number of adjacent swaps between different messages that could have produced it.

Level: Medium6 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Statement

Nikita received several messages today. One of them was the code word "spbsu". Any number of other messages may have come before and after the code word. Each of the other messages is an arbitrary string of lowercase English letters.

All messages were sent one by one over a secret channel, so the string in the channel was initially the concatenation of all messages.

However, the channel may add noise, since different messages can interfere with each other. The noise takes the form of swaps. In each swap, the channel picks two adjacent letters that originally belonged to different messages and exchanges them. The relative order of letters from the same message is preserved.

After all swaps, Nikita receives the resulting string. Given that string, find the minimum possible number of swaps the channel made.

Input

The first line contains a single integer $n$ , the number of received characters ( $5 \leq n \leq 10^5$ ).

The next line contains a string $s$ of $n$ lowercase English letters, the string Nikita received. It is guaranteed that $s$ is the result of the process described above.

Output

Output a single integer, the answer to the problem.

Examples2

Example 1
Input
```
6
spbssu
```
Expected output
```
1
```
Example 2
Input
```
15
spongebaseurban
```
Expected output
```
11
```