A Sorting Problem
InterviewTime limit3sMemory limit1024 MB
Given a permutation of 1 to n, you may swap two elements only when their values differ by 1; find the minimum number of such swaps to sort the array.
- Level
Medium6 of 10
- Topics
- Sorting, Greedy, Math, Implementation
- Solved
- No attempts yet
Problem
You are given an array [p[1], p[2], ..., p[n]]. All the numbers in the array are distinct, and they are positive integers between 1 and n. You can only perform the following operation on the array: pick two indices x and y such that |p[x]−p[y]| = 1, then swap the values of p[x] and p[y]. You want to sort this array in ascending order, that is, make p[i] = i for all i ∈ {1, 2, ..., n}. For example, the array [p[1] = 2, p[2] = 3, p[3] = 1] can be sorted in two operations.
- Swap p[1] and p[3]. The array becomes [p[1] = 1, p[2] = 3, p[3] = 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.
Write a program that computes the minimum number of operations needed to sort the given array in ascending order.
Input
The input consists of two lines. The first line contains one integer n. The second line contains n space-separated numbers p[1], p[2], ..., p[n] representing the array [p[1], p[2], ..., p[n]].
Output
Print one number, the minimum number of operations required to sort the given array.
Constraints
- 1 < n ≤ 200000.
- 1 ≤ p[i] ≤ n.
- All p[i] are distinct.