You are given a list that contains a permutation of the numbers 1 \dots n, where n is even. Your task is to rearrange the numbers so that all the numbers in the first half are smaller than all the numbers in the second half. In each step, you can swap two adjacent numbers. What is the minimum number of swaps needed?
You may assume that n is at most 10^5. The goal is an algorithm with time complexity O(n) or O(n \log n).
In a file semisort.py, implement a function solve that returns the minimum number of swaps.
def solve(t):
# TODO
if __name__ == "__main__":
print(solve([2, 1, 4, 3])) # 0
print(solve([5, 3, 4, 1, 6, 2])) # 6
print(solve([6, 5, 4, 3, 2, 1])) # 9
print(solve([10, 1, 9, 2, 8, 3, 7, 4, 6, 5])) # 15
Explanation: On the list [2,1,4,3], the numbers in the first half, 2 and 1, are already smaller than the numbers in the second half, 4 and 3. The list [5, 3, 4, 1, 6, 2] can be rearranged with 6 swaps. One optimal solution is: [5, 3, 4, 1, 6, 2] \rightarrow [5, 3, 4, 1, 2, 6] \rightarrow [3, 5, 4, 1, 2, 6] \rightarrow [3, 5, 1, 4, 2, 6] \rightarrow [3, 1, 5, 4, 2, 6] \rightarrow [3, 1, 5, 2, 4, 6] \rightarrow [3, 1, 2, 5, 4, 6].