Luna 有一个疯狂的想法。她将她的 $2n$ 个朋友排成一列，并给每个人分配了一个 $1$ 到 $n$ 之间的整数。每个数字恰好被使用两次。每一对拥有相同数字的朋友组成一对情侣。
Luna 想要安排这 $n$ 对情侣去约会。然而，这并不简单。为了让一对情侣去约会，组成这对情侣的两个朋友必须在队伍中相邻，即他们之间不能有其他人。
Luna 可以采取两种操作：
- 她可以交换队伍中任意两个相邻的朋友。
- 如果一对情侣在队伍中相邻，Luna 可以让他们去约会。这会将这对情侣从队伍中移除。剩下的朋友会移动以填补队伍中的空隙。
这些操作可以以任何顺序执行。例如，她可以先进行一些交换，然后让几对朋友去约会，然后再回到交换操作。
请找出并输出让所有人都能去约会所需的最少操作次数。
输入格式
第一行包含一个整数 $n$。
第二行包含 $2n$ 个以空格分隔的整数 $a_i$ ($1 \le a_i \le n$)，表示朋友们在长队中收到的数字序列。
输出格式
输出一行，包含 Luna 为了让每一对情侣都能去约会所需执行的最少操作次数。
子任务
子任务 1 (7 分)：对于每一对情侣，他们之间没有其他人，且 $1 \le n \le 100$。
子任务 2 (8 分)：对于每一对情侣，他们之间最多有一个人，且 $1 \le n \le 100$。
子任务 3 (11 分)：队伍中的前 $n$ 个朋友收到的整数为 $1$ 到 $n$，每个恰好出现一次，顺序不一定。此外，$1 \le n \le 3000$。
子任务 4 (16 分)：队伍中的前 $n$ 个朋友收到的整数为 $1$ 到 $n$，每个恰好出现一次，顺序不一定。此外，$1 \le n \le 500\,000$。
子任务 5 (22 分)：$1 \le n \le 3000$。
子任务 6 (36 分)：$1 \le n \le 500\,000$。
样例
样例输入 1
3 3 1 2 1 2 3
样例输出 1
4
样例输入 2
5 5 1 2 3 2 3 1 4 5 4
样例输出 2
7
说明
在第一个样例中，Luna 可以先交换第三个和第四个朋友。交换后队伍变为：3 1 1 2 2 3。
然后，她可以让数字为 1 的情侣和数字为 2 的情侣去约会（顺序不限）。一旦她这样做，数字为 3 的两个朋友现在在队伍中相邻，Luna 也可以让他们去约会。
总的来说，这个方案需要 4 次操作：一次交换和三次约会。