Description

There are $n$ kids standing in a line. Now we want to arrange them in non-decreasing order of height (from short to tall), but each operation can only swap two adjacent kids.

Each kid has an "unhappiness" value. At the beginning, every kid’s unhappiness is $0$.

If a kid is asked to swap for the first time, their unhappiness increases by $1$. If they are asked to swap for the second time, their unhappiness increases by $2$ (so the total becomes $3$), and so on. In general, when a kid is asked to swap for the $k$-th time, their unhappiness increases by $k$.

Find the minimum possible total unhappiness (the sum of all kids’ unhappiness values) after making all kids line up from short to tall.

If two kids have the same height, it does not matter which one stands in front of the other.

Input Format

The first line contains an integer $n$, the number of kids.

The second line contains $n$ integers $H_1,H_2 \cdots H_n$, where $H_i$ is the height of the $i$-th kid.

Output Format

Output one line containing one integer, the minimum possible total unhappiness.

3
3 2 1

9

Hint

[Sample Explanation]

First swap the kids with heights $3$ and $2$, then swap the kids with heights $3$ and $1$, and then swap the kids with heights $2$ and $1$. Each kid’s unhappiness is $3$, so the total is $9$.

[Constraints]

For $10\%$ of the testdata, $1 \le n \le 10$.

For $30\%$ of the testdata, $1 \le n \le 1000$.

For $50\%$ of the testdata, $1 \le n \le 10000$.

For $100\%$ of the testdata, $1 \le n \le 100000$, $0 \le H_i \le 1000000$.

Time limit: 1 second. Memory limit: 256 MB. Lanqiao Cup 2014, the 5th Provincial Contest.

Translated by ChatGPT 5