题目描述

Sashka 有一个排列，而且不是普通排列，而是一个长度为 $2N$ 的排列：

它由 $1$ 到 $2N$ 的所有整数各出现一次组成。

她想把这个排列按升序排序。为此，她可以使用两类交换操作。

操作 1

选择两个整数 $x,y$，满足 $1\le x,y\le N$，然后同时交换：

以及

也就是说，可以把第 $x$ 个长度为 $2$ 的块和第 $y$ 个长度为 $2$ 的块整体交换。

该操作费用为 $0$ 元。

操作 2

选择一个整数 $x$，满足 $1\le x<2N$，然后交换相邻两个元素：

该操作费用为 $1$ 元。

Sashka 有一个限制：一旦她使用过操作 2，就不能再使用操作 1。也就是说，她必须先进行若干次操作 1，然后再进行若干次操作 2。

她想知道，为了把排列排成升序，最少需要花费多少元。

请你编写程序求出这个最小费用。

输入格式

第一行输入一个正整数 $N$。

第二行输入 $2N$ 个整数：

输出格式

输出一个整数，表示最小可能费用。

数据范围

• $1 \le N \le 10^5$
• $1 \le p_i \le 2N$
• 对任意 $i\ne j$，有 $p_i\ne p_j$

子任务

只有当某个子任务及其所依赖的子任务全部通过时，才能获得该子任务的分数。

样例 1

输入

1
2 1

输出

1

样例 2

输入

3
6 5 1 4 3 2

输出

4

难度评估

操作 1 只能交换长度为 $2$ 的块，不能改变每个块内部两个元素的相对顺序；操作 2 的最小费用等于最终排列中的逆序数。因此题目可以理解为：任意重排这些长度为 $2$ 的块，使重排后的总逆序数最小。

题解中的关键结论是：先把每个块内部较小的数放前面，若原来块内逆序则答案先加 $1$；随后把这些二元组按某个合法关键字排序，例如按 max(a,b) 或按 a+b 排序，都可以得到最优块顺序。最后对拼接后的长度 $2N$ 序列计算逆序数即可。

实现本身并不长：排序二元组，然后用归并排序或树状数组统计逆序数。但正确性证明不直观，尤其是为什么这样排序二元组一定最优。

建议 CF 评分：2200。