AT_arc225_d.Gap Swap (easy)

This problem has a similar setting to Problem E, but the cost of the operation is different.

There is a permutation $P$ of $(1,2,\ldots,N)$. You can perform the following operation on $P$.

• Choose integers $i$ and $j$ satisfying $1 \le i < j \le N$. Here, $P_k=k$ must hold for every integer $k$ satisfying $i < k < j$. Then, swap $P_i$ and $P_j$.
  This operation incurs a cost of $\boldsymbol{j-i}$.

Note that if $i+1=j$, there is no integer $k$ satisfying $i<k<j$, so the operation can always be performed. Therefore, there always exists a sequence of operations that sorts $P$ into ascending order.

Find the minimum total cost required to sort $P$ into ascending order.

本题的设定与问题 E 类似，但操作的代价不同。

给定一个 $(1,2,\ldots,N)$ 的排列 $P$。你可以对 $P$ 执行以下操作：

• 选择满足 $1 \le i < j \le N$ 的整数 $i$ 和 $j$，要求对每个满足 $i < k < j$ 的整数 $k$，均有 $P_k = k$。然后交换 $P_i$ 和 $P_j$。
  此操作的代价为 $\boldsymbol{j-i}$。

注意：若 $i+1=j$，则不存在满足 $i<k<j$ 的整数 $k$，因此该操作总可执行。故总存在一系列操作能将 $P$ 排序为升序。

求将 $P$ 排序为升序所需的最小总代价。

The input is given from Standard Input in the following format:

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

输入从标准输入给出，格式如下：

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

Output the answer.

输出答案。

Sample 1 Explanation:
For example, by performing two operations as follows, $P$ can be sorted into ascending order with a total cost of $6$.

• First operation: choose $i=4, j=5$, and swap $P_4, P_5$. This costs $1$.
• Second operation: choose $i=1, j=6$, and swap $P_1, P_6$. This costs $5$.

$P$ cannot be sorted into ascending order with a cost less than $6$, so the answer is $6$.

Sample 2 Explanation:
The required total cost can be $0$.

Constraints

• $2 \le N \le 5\times 10^5$
• $1 \le P_i \le N$
• $P$ is a permutation of $(1,2,\ldots,N)$.
• All input values are integers.

样例 1 解释：
例如，通过执行以下两次操作，可将 $P$ 排序为升序，总代价为 $6$。

• 第一次操作：选择 $i=4, j=5$，交换 $P_4$ 与 $P_5$。此次操作代价为 $1$。
• 第二次操作：选择 $i=1, j=6$，交换 $P_1$ 与 $P_6$。此次操作代价为 $5$。

无法以小于 $6$ 的总代价将 $P$ 排序为升序，因此答案为 $6$。

样例 2 解释：
所需总代价可以为 $0$。

约束条件

• $2 \le N \le 5\times 10^5$
• $1 \le P_i \le N$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列。
• 所有输入值均为整数。