P15931 [TOPC 2021] A Sorting Problem

给定一个数组 $[p[1], p[2], \dots, p[n]]$，其中所有数互不相同，且均为 $1$ 到 $n$ 之间的正整数。你只能对数组执行以下操作：选择两个下标 $x$ 和 $y$，使得 $|p[x] - p[y]| = 1$，然后交换 $p[x]$ 和 $p[y]$ 的值。我们希望将这个数组按升序排序，即对于所有 $i \in \{1, 2, \dots, n\}$，使 $p[i] = i$。例如，我们可以通过两次操作将数组 $[p[1] = 2, p[2] = 3, p[3] = 1]$ 排序： 1. 交换 $p[1]$ 和 $p[3]$。数组变为 $[p[1] = 1, p[2] = 3, p[3] = 2]$。 2. 交换 $p[2]$ 和 $p[3]$。数组变为 $[p[1] = 1, p[2] = 2, p[3] = 3]$，此时数组已按升序排序。 请编写一个程序，计算将给定数组按升序排序所需的最少操作次数。

输入包含两行。第一行包含一个整数 $n$。第二行包含 $n$ 个空格分隔的数 $p[1], p[2], \dots, p[n]$，表示数组 $[p[1], p[2], \dots, p[n]]$。

输出一个整数，表示将给定数组排序所需的最少操作次数。

- $1 < n \leq 200000$ - $1 \leq p[i] \leq n$ - 所有 $p[i]$ 互不相同。 翻译由 DeepSeek V3.2 完成