Minimum Swaps to Sort Books

You are given a list of books arranged by their heights. The books need to be sorted in non-decreasing order by height. Your task is to determine the minimum number of adjacent swaps required to sort the list.

This problem can be solved by computing the number of inversions in the list of book heights. An inversion is a pair of indices \( (i, j) \) such that \( i a_j \). Using a modified merge sort algorithm, you can count the number of inversions (swaps) in \( O(n \log n) \) time.

Input format: The first line contains an integer \( t \), denoting the number of test cases. For each test case, the first integer is \( n \) (the number of books), followed by \( n \) space-separated integers representing the heights of the books.

Output format: For each test case, output a single integer which is the minimum number of swaps required to sort the list.

inputFormat

The input will be given via stdin and will contain:

• An integer \( t \) representing the number of test cases.
• For each test case, an integer \( n \) representing the number of books, followed by \( n \) space-separated integers denoting the heights of the books.

outputFormat

For each test case, output the minimum number of adjacent swaps required to sort the list of books in non-decreasing order. Each result should be printed on a separate line on stdout.

1
4
4 3 1 2

5