Minimum Adjacent Swaps to Sort Books

You are given an array of integers representing the heights of books. The objective is to sort the array in non-decreasing order by only swapping adjacent elements.

Formally, let \(a_1, a_2, \ldots, a_n\) be the array of book heights. A single operation consists of swapping \(a_i\) and \(a_{i+1}\) for some valid index \(i\). Your task is to determine the minimum number of such adjacent swaps required to sort the array.

Example:

• For the array [3, 1, 2, 4], the minimum number of adjacent swaps is 2.
• For the array [4, 3, 2, 1], the minimum number of adjacent swaps is 6.

Hint: The problem essentially asks you to count the number of inversions in the array.

inputFormat

The first line contains a single integer \(n\) representing the number of books.

The second line contains \(n\) space-separated integers denoting the heights of the books.

outputFormat

Output a single integer, the minimum number of adjacent swaps required to sort the array in non-decreasing order.

## sample

4
3 1 2 4

2

</p>