AT_arc225_e [ARC225E] Gap Swap (hard)

**本题与 D 题设置类似，但操作的代价不同。** 给定一个长度为 $N$ 的排列 $P$，其中 $P$ 是 $1,2,\ldots,N$ 的一个排列。你可以对 $P$ 执行如下操作： - 选择整数 $i$ 和 $j$，满足 $1 \le i < j \le N$，并且对于满足 $i

输入由标准输入给出，格式如下： > $N$ $P_1$ $P_2$ $\cdots$ $P_N$

输出答案。

## 样例解释 1 例如，可以通过如下两步操作，将 $P$ 排成升序，总代价为 $2$： - 第一步：选择 $i=4, j=5$，交换 $P_4$ 和 $P_5$，代价为 $1$。 - 第二步：选择 $i=1, j=6$，交换 $P_1$ 和 $P_6$，代价为 $1$。 无法以低于 $2$ 的代价将 $P$ 排成升序，所以答案是 $2$。 ## 样例解释 2 所需总代价可能为 $0$。 ## 约束条件 - $2 \le N \le 5\times 10^5$ - $1 \le P_i \le N$ - $P$ 是 $(1,2,\ldots,N)$ 的一个排列。 - 所有输入均为整数。 由 ChatGPT 5 翻译