What Goes Up Must Come Down

Time limit2sMemory limit512 MB

Summary

Rearrange the cards by adjacent swaps into a bitonic order with the fewest moves, counting inversions by value.

Level: Hard8 of 10
Topics: Divide and conquer, Sorting, Greedy, Bit manipulation
Solved: No attempts yet

Problem

Several cards with numbers printed on them are lined up on the table.

We want to change their order so that the first part is in non-decreasing order of the numbers and the rest is in non-increasing order. For example, (1, 2, 3, 2, 1), (1, 1, 3, 4, 5, 9, 2), and (5, 3, 1) are acceptable orders, but (8, 7, 9) and (5, 3, 5, 3) are not.

Formally, let $n$ be the number of cards and let $b_i$ be the number printed on the card at the $i$ -th position ( $1 \le i \le n$ ) after reordering. There must exist $k \in \{1, \ldots, n\}$ such that $(b_i \le b_{i+1}\ \forall i \in \{1, \ldots, k-1\})$ and $(b_i \ge b_{i+1}\ \forall i \in \{k, \ldots, n-1\})$ .

The only operation allowed for reordering is to swap the positions of an adjacent pair of cards. We want to know the minimum number of swaps required to complete the reorder.

Input

The input consists of a single test case of the following format.

n
a1 . . . an

An integer $n$ in the first line is the number of cards ( $1 \le n \le 100\ 000$ ). The integers $a_1$ through $a_n$ in the second line are the numbers printed on the cards, in the order of their original positions ( $1 \le a_i \le 100\ 000$ ).

Output

Output in a line the minimum number of swaps required to reorder the cards as specified.

Examples4

Example 1
Input
```
7
3 1 4 1 5 9 2
```
Expected output
```
3
```
Example 2
Input
```
9
10 4 6 3 15 9 1 1 12
```
Expected output
```
8
```
Example 3
Input
```
8
9 9 8 8 7 7 6 6
```
Expected output
```
0
```
Example 4
Input
```
6
8 7 2 5 4 6
```
Expected output
```
4
```