Preparing NOJ # A Sorting Problem

3000ms 1048576K

## Description:

You are given an array $[p, p, ..., 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=2,p=3,p=1]$ in two operations:

1. Swap $p$ and $p$. The array becomes $[p=1,p=3,p=2]$.
2. Swap $p$ and $p$. The array becomes $[p=1,p=2,p=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.

## Input:

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

• $1< n\le 200000$.
• $1\le p[i] \le n$.
• All $p[i]$ are distinct.

## Output:

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

## Sample Input:

3
1 3 2


## Sample Output:

1


## Sample Input:

5
5 3 2 1 4


## Sample Output:

7


Info Provider CodeForces Gym

Code GYM103373C

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:46:00

Related

Nothing Yet