Description

You are given a positive integer $n$ and a string consisting of $2n$ lowercase letters.

Swapping two adjacent letters in the string is considered one operation. Find the minimum number of operations needed to make the first $n$ lowercase letters of the original string exactly the same as the last $n$ lowercase letters.

Input Format

The first line contains a positive integer $n$.

The second line contains a string of length $2n$ consisting of lowercase letters. The testdata guarantees that each letter appears an even number of times.

Output Format

Output the minimum number of operations.

3
koeeok

3

3
kekoeo

1

4
soolnlsn

4

Hint

[Explanation for Sample 3]

One optimal sequence with the minimum number of operations:

$\texttt{soolnlsn} \to \texttt{so\red{lo}nlsn} \to \texttt{sol\red{no}lsn} \to \texttt{\red{os}lnolsn} \to \texttt{o\red{ls}nolsn}$

[Constraints and Notes]

This problem uses bundled subtasks.

• Subtask 1 (10 pts): The first $n$ letters of the string are all $\texttt a$, and the last $n$ letters are all $\texttt b$.
• Subtask 2 (20 pts): Each letter appears at most twice in the string.
• Subtask 3 (20 pts): The multiset of letters in the first $n$ positions is exactly the same as in the last $n$ positions, but the order may be different.
• Subtask 4 (20 pts): $1 \le n \le 1000$.
• Subtask 5 (40 pts): No special restrictions.

For $100\%$ of the testdata, $1 \le n \le 10^5$.

[Hints and Additional Information]

Translated from COCI 2021-2022 CONTEST #3 Task 4 Ekoeko.

The scoring of this problem follows the original COCI problem settings, with a full score of $110$.

Translated by ChatGPT 5