Ekoeko

Time limit1sMemory limit512 MB

Summary

Given a 2n-letter string where each letter appears an even number of times, find the minimum adjacent swaps to rearrange it into a word that is two identical halves.

Level: Medium7 of 10
Topics: Greedy, Sorting, Array, String
Solved: No attempts yet

Problem

You must be familiar with the story of an alien called Eko Eko, who got his name because of a malfunction in his translation device. The little alien is back on Earth to help earthlings clean up after the Advent. However, Eko Eko's translation device has stopped working again.

This time, the device not only repeats a word but also changes the order of the letters in the word. For example, the word “slon” first becomes “slonslon”, and then, by changing the order of the letters, it can become “slosnoln” or “soolnlsn” and so on. The amount of gold needed to repair Eko Eko's device depends on the number of swaps of adjacent characters needed to turn the badly translated word into a word made from a repetition.

For example, if Eko Eko's device translates a word to “soolnlsn”, four swaps of adjacent characters are enough to obtain the repetition word “olsnolsn” (see the clarification of the third example), so four pieces of gold are enough to repair his device. The word obtained from such swaps is not necessarily the word Eko Eko originally wanted to say. This does not affect the amount of gold needed to repair his device.

You want to help Eko Eko, but if you steal too much of your mother's jewelry you will not get a Christmas present. So, given a word produced by Eko Eko's translation device, you want to determine the minimum number of swaps of adjacent characters needed to obtain a word made from a repetition.

Input

The first line contains a positive integer $n$ , the length of the word Eko Eko is trying to say.

The second line contains a sequence of $2n$ characters, each a lowercase letter of the Latin alphabet, representing the word produced by Eko Eko's translation device. Each letter appears an even number of times.

Output

Print, on a single line, the minimum number of swaps of adjacent characters needed to turn Eko Eko's word into a word made from a repetition.

Constraints

In all subtasks, $1 ≤ n ≤ 100\,000$ .

Hint

Clarification of the third example: one way to get from soolnlsn to a repetition word using four swaps is

soolnlsn → solonlsn → solnolsn → oslnolsn → olsnolsn

Examples3

Example 1
Input
```
3
koeeok
```
Expected output
```
3
```
Example 2
Input
```
3
kekoeo
```
Expected output
```
1
```
Example 3
Input
```
4
soolnlsn
```
Expected output
```
4
```