P8030 [COCI 2021/2022 #3] Ekoeko

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.

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 the minimum number of operations.

**[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](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 4 Ekoeko_.** **The scoring of this problem follows the original COCI problem settings, with a full score of $110$.** Translated by ChatGPT 5