Minimum Cost to Sort
You are given an array of N distinct integers. You want to sort this array in non-decreasing order. The only operation allowed is to swap two adjacent elements. Each swap has a cost equal to the absolute difference between the two elements being swapped. Find the minimum total cost to sort the array.
Input
The first line contains an integer N. The second line contains N space-separated integers representing the array.
Output
Print a single integer, the minimum total cost to sort the array.
Constraints
1 <= N <= 1000 -1000 <= arr[i] <= 1000 for all i. All elements in the array are distinct.
Example 1
3 3 1 2
3
Initial array: [3, 1, 2]. Sorted array: [1, 2, 3]. Pass 1: Compare 3 and 1: 3 > 1. Swap. Cost = abs(3-1) = 2. Array becomes [1, 3, 2]. Total cost = 2. Compare 3 and 2: 3 > 2. Swap. Cost = abs(3-2) = 1. Array becomes [1, 2, 3]. Total cost = 2 + 1 = 3. Pass 2: Compare 1 and 2: 1 < 2. No swap. Array is
Example 2
4 1 2 3 4
0
The array is already sorted. No swaps are needed. The total cost is 0.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 3 1 2
4 1 2 3 4