Problem Description

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 required to make the first $n$ letters identical to the last $n$ letters.

Input Format

The first line contains a positive integer $n$.

The second line contains a string of $2n$ lowercase letters. It is guaranteed that each letter appears an even number of times.

Output Format

Output the minimum number of operations required.

Sample Input and Output

Sample Input #1

3
koeeok

Sample Output #1

3

Sample Input #2

3
kekoeo

Sample Output #2

1

Sample Input #3

4
soolnlsn

Sample Output #3

4

Notes

Sample 3 Explanation

One of the minimum operation schemes:

$\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}$

Data Range and Constraints

This problem uses subtask-based scoring.

• Subtask 1 (10 pts): The first $n$ letters 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 first $n$ letters and the last $n$ letters have the same composition but possibly different orders.
• Subtask 4 (20 pts): $1 \le n \le 1000$.
• Subtask 5 (40 pts): No special restrictions.

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

Hints and References

This problem is translated from COCI 2021-2022 CONTEST #3 Task 4 Ekoeko.

The score distribution follows the original COCI settings, with a maximum score of $110$.

见题面 Input 部分

见题面 Output 部分