Counter-Clockwise Subarray Rotation Sorting

You are given an array A of n integers. In one operation, you can choose a contiguous subarray of A and rotate it counter-clockwise (i.e. take the first element of the subarray and move it to the end of that subarray). The goal is to determine the minimum number of such operations required to sort the array in non-decreasing order.

An important insight is that the minimum number of operations is equal to the total number of inversions in the array. Here, an inversion is defined as a pair of indices \((i, j)\) such that \(i < j\) and \(a_i > a_j\). This is expressed in LaTeX as:

[ \text{Inversions} = |{(i,j) \mid i < j \text{ and } a_i > a_j}|. ]

Your task is to compute this inversion count, which corresponds to the minimum number of counter-clockwise subarray rotations needed to sort the array.

inputFormat

The input is read from stdin and consists of two parts:

• The first line contains a single integer n, representing the number of elements in the array.
• The second line contains n space-separated integers, the elements of the array.

outputFormat

Output a single integer to stdout, which is the minimum number of counter-clockwise subarray rotations required to sort the array (i.e. the total inversion count).

## sample

5
3 1 4 2 5

3

</p>