#215016. [ICPC 2018 Yokohama R] What Goes Up Must Come Down

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

We'd like to change their order so that first some are in non-decreasing order of the numbers on them, and the rest are in non-increasing order. For example, , , and are acceptable orders, but and are not.

To put it formally, with the number of cards and the number printed on the card at the -th position () after reordering, there should exist such that () and () hold.

For reordering, the only operation allowed at a time is to swap the positions of an adjacent card pair. We want to know the minimum number of swaps required to complete the reorder.

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

An integer in the first line is the number of cards (). Integers through in the second line are the numbers printed on the cards, in the order of their original positions ().

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

样例输入 1

7
3 1 4 1 5 9 2

样例输出 1

3

样例输入 2

9
10 4 6 3 15 9 1 1 12

样例输出 2

8

样例输入 3

8
9 9 8 8 7 7 6 6

样例输出 3

0

样例输入 4

6
8 7 2 5 4 6

样例输出 4

4