Problem Statement

This problem has a similar setting to Problem D, 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{1}$.

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.

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.

Input

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

N
P_1 P_2 \ldots P_N

Output

Output the answer.