← 返回 akunacapital 的题目列表Minimum Swaps to Order Items
类型：online_judge
In HackLand, each item in a shop has a unique popularity rating. The shopkeeper can reorder the items to decrease in popularity from left to right by swapping any 2 items in one operation. Determine the minimum number of operations required to reorder the items correctly.
Input Format:
The first line contains an integer n, the size of the array popularity.
The next n lines each contain an integer popularity[i].
Output Format:
Return an integer that represents the minimum number of swaps required to order the items properly.
Constraints:
1 ≤ n ≤ 2 x 10^5
1 ≤ popularity[i] ≤ n
Example:
Input:
4
3
4
1
2
Output:
2
In this example, swap 3 and 4 to get [4, 3, 1, 2], then swap 1 and 2 to get [4, 3, 2, 1], requiring 2 operations in total.
Example
Input
4
3
4
1
2