Minimum Adjacent Swaps to Sort Books

You are given a sequence of books represented by their identification numbers. Your task is to determine the minimum number of adjacent swaps required to sort the books in non-decreasing order.

The problem can be viewed as counting the number of inversion pairs in the sequence. For example, if the input sequence is [4, 3, 2, 1, 5], then the minimum number of swaps required is 6.

Note: Each swap operation only allows you to swap two adjacent books.

inputFormat

The input consists of a single test case. The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of books. The second line contains n space-separated integers representing the identification numbers of the books.

outputFormat

Output a single integer – the minimum number of adjacent swaps required to sort the list of books in non-decreasing order.

5
4 3 2 1 5

6