Preparing NOJ

A Sorting Problem

3000ms 1048576K

Description:

You are given an array $$$[p[1], p[2], ..., 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.

Input:

The input contain two lines. The first line contains one integer $$$n$$$. The second lines contain $$$n$$$ space-saparated numbers $$$p[1],p[2],\dots,p[n]$$$ representing the array $$$[p[1], p[2],\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

CodeForces Gym

Provider CodeForces Gym

Origin 2021 ICPC Asia Taiwan Online Programming Contest

Code GYM103373C

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:46:00

Related

Nothing Yet