Minimum Adjacent Swaps to Sort Books

Given n books arranged in a row with unique heights, your task is to determine the minimum number of adjacent swaps required to sort the books in non-decreasing order. An adjacent swap means exchanging two consecutive books.

The problem can be formulated as follows: Given an array \(a_1, a_2, \ldots, a_n\) of integers, find the minimum number of swaps of adjacent elements required to obtain a sorted array \(a_1' \leq a_2' \leq \ldots \leq a_n'\). For example, if \(n = 3\) and the heights are [3, 1, 2], the sorted order is [1, 2, 3] which requires 2 swaps.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n, representing the number of books.
• The second line contains n space-separated integers representing the heights of the books.

outputFormat

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

3
3 1 2

2