P15931 [TOPC 2021] A Sorting Problem

You are given an array $[p[1], p[2], \dots, p[n]]$ where all the numbers in the array are distinct. In addition, the numbers are positive integers between 1 and $n$. You can only perform the following operations on the array: Pick two indices $x$ and $y$ such that $|p[x] - p[y]| = 1$, and then swap the values of $p[x]$ and $p[y]$. We now want to sort this array in ascending order. That is, to make $p[i] = i$ for all $i \in \{1, 2, \dots, n\}$. For example, we can sort the array $[p[1] = 2, p[2] = 3, p[3] = 1]$ in two operations: 1. Swap $p[1]$ and $p[3]$. The array becomes $[p[1] = 1, p[2] = 3, p[3] = 2]$. 2. Swap $p[2]$ and $p[3]$. The array becomes $[p[1] = 1, p[2] = 2, p[3] = 3]$ which is sorted in ascending order. Please write a program to compute the minimum number of operations to sort a given array in ascending order.

The input contain two lines. The first line contains one integer $n$. The second lines contain $n$ space-separated numbers $p[1], p[2], \dots, p[n]$ representing the array $[p[1], p[2], \dots, p[n]]$

Output only one number that denotes the minimum number of operations required to sort the given array.

- $1 < n \leq 200000$. - $1 \leq p[i] \leq n$. - All $p[i]$ are distinct.