Description
In the ancient kingdom of Numeria, a land ruled by the arcane order of Mathemagicians, you are challenged to a game of "Consecutive Swap Chess". This game is played on a linear board numbered from 1 to n, with each square uniquely occupied by enchanted stones numbered from 1 to n. The initial arrangement of the stones is given as an array: [p[1],p[2],...,p[n]].
The Mathemagicians allow you to make moves under a magical constraint: You may only swap two stones if their numerical difference is exactly one, suggesting a mystical bond between consecutive numbers, which means pick two indices x and y such that |p[x] − p[y]| = 1.Your task is to appease the Mathemagicians by transforming the board into a state of ascending tranquility, where each stone p[i] aligns perfectly with its board position i (i.e. p[i] = i for all i ∈ {1,2,…,n})
- Swap the stones in positions 1 and 3 (i.e., stones 2 and 1). The board becomes [p[1]=1,p[2]=3,p[3]=2].
- Swap the stones in positions 2 and 3 (i.e., stones 3 and 2). The board then becomes [p[1]=1,p[2]=2,p[3]=3], achieving the state of ascending tranquility.
Hint:
- Understanding Inversions:
Delve into the concept of inversion pairs in an array, where an inversion occurs when a larger number precedes a smaller one. For instance, in the array [3,1,2], there are two inversions: 3 precedes 1 and 3 precedes 2. Understanding and identifying these inversions is pivotal in developing a solution for sorting the array. - Test Case 1~3 for O(n2) or O(n3) Complexity:
Consider designing a test case that allows for a solution with a time complexity of O(n3). This might involve checking each possible pair multiple times, ideal for a smaller dataset where such complexity is manageable. - Test Case 4~5 for O(nlogn) Complexity:
Prepare a test case that is efficiently solvable using O(nlogn)\ algorithms. This often involves techniques like divide and conquer, which are suitable for sorting problems and can handle larger data sets effectively.
Input
The input consists of two lines: The first line contains a single integer n, representing the size of the array. The second line contains n space-separated integers [p[1],p[2],...,p[n]], which represent the elements of the array.
- 1 < n ≦ 200,000
- 1 ≦ p[i] ≦ n
- Each p[i] is distinct and appears exactly once in the array.
Output
Output only one number that denotes the minimum number of operations required to sort the given array.
Please print ''\n'' after your output number