题目描述

给定一个正整数 $n$ 和一个由 $2n$ 个小写字母组成的字符串。

交换字符串的相邻两个字母视为一次操作。求使得原串的前 $n$ 个小字母和后 $n$ 个完全相同所需的最少操作次数。

输入格式

第一行，一个正整数 $n$。

第二行，一个由 $2n$ 个小写字母组成的字符串。数据保证每个字母均出现偶数次。

输出格式

输出最少操作次数。

3
koeeok

3

3
kekoeo

1

4
soolnlsn

4

提示

【样例 3 解释】

一种操作次数最少的方案：

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

【数据规模与约定】

本题采用子任务捆绑测试。

• Subtask 1（10 pts）：字符串前 $n$ 个字母均为 $\texttt a$，后 $n$ 个均为 $\texttt b$。
• Subtask 2（20 pts）：每个字母在字符串中至多出现两次。
• Subtask 3（20 pts）：前 $n$ 个字母和后 $n$ 个字母的组成完全相同，但顺序可能不同。
• Subtask 4（20 pts）：$1 \le n \le 1000$。
• Subtask 5（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$。

【提示与说明】

题目译自 COCI 2021-2022 CONTEST #3 Task 4 Ekoeko。

本题分值按 COCI 原题设置，满分 $110$。