题目描述

有 $2n$ 个元素，编号为 $1, 2, \dots, 2n$。目标是将它们配成 $n$ 对 $\{1, 2\}, \{3, 4\}, \dots, \{2n-1, 2n\}$（每个数对内的顺序无关，数对之间的顺序也无关）。

当前给定一个排列 $p_1, p_2, \dots, p_{2n}$，其中相邻的两个元素组成当前的一对：$\{p_1, p_2\}$ 为一对，$\{p_3, p_4\}$ 为一对，以此类推。

每次操作可以选择排列中的任意两个位置，交换这两个位置上的元素。求最少需要多少次交换，才能使得最终的 $n$ 对数恰好是目标配对的 $n$ 个集合。

输入格式

第一行一个整数 $n$。

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

输出格式

输出一行一个整数，表示最少交换次数。

样例

3
3 5 4 6 2 1

1

4
1 2 3 4 5 6 7 8

0

4
2 1 4 3 6 5 8 7

0

样例解释

对于样例 1：当前排列为 $[3, 5, 4, 6, 2, 1]$，当前配对为 $\{3, 5\}, \{4, 6\}, \{2, 1\}$。目标配对为 $\{1, 2\}, \{3, 4\}, \{5, 6\}$。交换位置 $2$ 和 $3$（$5$ 和 $4$），得到 $[3, 4, 5, 6, 2, 1]$，此时配对为 $\{3, 4\}, \{5, 6\}, \{1, 2\}$，满足目标。仅需 $1$ 次交换。

对于样例 2：当前排列已完全有序，每一对都已经是目标配对，不需要交换。

对于样例 3：虽然每对内部顺序颠倒（$\{2,1\}$ 而非 $\{1,2\}$），但集合仍是正确的目标配对，不需要交换。

数据范围与约定

对于所有数据，$1 \le n \le 10^5$，$p_1, p_2, \dots, p_{2n}$ 是 $1$ 到 $2n$ 的排列。

下发样例

[下发样例下载](file://sample.zip)