题目描述

有 $2n$ 个位置，填入 $1$ 到 $2n$ 的一个排列。标准的配对方式为 $\{1,2\}$ 一对、$\{3,4\}$ 一对……$\{2n-1,2n\}$ 一对。

现在给出一个打乱的排列 $p_1,p_2,\dots,p_{2n}$，当前配对方式为 $\{p_1,p_2\}$ 一对、$\{p_3,p_4\}$ 一对……每对内部顺序不限，每对之间的排列顺序也不限。

你每次操作可以交换任意两个位置上的数。求最少操作次数，使得最终排列中，每个标准配对 $\{2i-1,2i\}$ 的两个数位于同一对中。

输入格式

第一行一个整数 $n$。

第二行 $2n$ 个整数 $p_1,p_2,\dots,p_{2n}$，保证是 $1$ 到 $2n$ 的排列。

输出格式

一行一个整数，表示最少操作次数。

3
3 5 4 6 2 1

1

4
1 4 2 3 5 6 7 8

1

样例解释

样例 $1$：当前配对 $(3,5),(4,6),(2,1)$。交换 $5$ 和 $4$ 得 $(3,4),(5,6),(2,1)$，即 $\{3,4\},\{5,6\},\{1,2\}$，每个标准配对都已成对。只需 $1$ 次。

样例 $2$：当前配对 $(1,4),(2,3),(5,6),(7,8)$。交换 $4$ 和 $2$ 得 $(1,2),(4,3),(5,6),(7,8)$ 即可。$1$ 次。

数据范围与约定

下发样例

下发样例下载