Minimizing Total Unhappiness in Adjacent Swaps

There are \(n\) children standing in a line. The goal is to arrange them in increasing order of their heights using only adjacent swaps. Each child has an initial unhappiness of \(0\). When a child is swapped for the first time, his unhappiness increases by \(1\); for the second swap by \(2\) (making his total unhappiness \(3\)), and so on. Formally, when a child is swapped for the \(k\text{-th}\) time, his unhappiness increases by \(k\), so that his total unhappiness becomes \(1+2+\cdots+k=\frac{k(k+1)}{2}\).

You are required to sort the children in non-decreasing order of their heights. If two children have the same height, their relative order does not matter.

Determine the minimum possible cumulative unhappiness across all children needed to achieve the sorted order.

inputFormat

The first line contains an integer \(n\) (\(1\le n \le 10^5\)) -- the number of children. The second line contains \(n\) space-separated integers representing the heights of the children.

outputFormat

Output a single integer representing the minimum total unhappiness required to sort the children in increasing order.

sample

2
2 1

2