Minimum Operations to Make Array Sorted
Given an array of N distinct integers, you can perform an operation: choose an index i (1 <= i < N) and swap a[i] and a[i-1]. The goal is to sort the array in non-decreasing order using the minimum number of such adjacent swaps. Count the total number of swaps required.
Input
The first line contains an integer N (2 <= N <= 200000). The second line contains N distinct integers, a_1, a_2, ..., a_N (-10^9 <= a_i <= 10^9).
Output
Print a single integer: the minimum number of adjacent swaps required to sort the array.
Constraints
2 <= N <= 200000
-10^9 <= a_i <= 10^9
All a_i are distinct.
Example 1
4 1 3 2 4
1
The pair (3, 2) is an inversion. One swap makes it sorted: 1 2 3 4.
Example 2
3 3 2 1
3
Pairs (3, 2), (3, 1), (2, 1) are inversions. Total 3 swaps needed: 3 2 1 -> 2 3 1 -> 2 1 3 -> 1 2 3.
Hints
Similar problems
- Minimum Absolute DifferenceEasy
- Maximum Non-overlapping IntervalsMedium
- Longest Subarray with Constant DifferenceMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
More topics: Arrays problems, Sorting problems, Greedy problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 1 3 2 4
3 3 2 1