Bitonic Ordering

Time limit2sMemory limit512 MB

Summary

Given a permutation of distinct cards, find the minimum number of adjacent swaps needed to make the sequence first increasing then decreasing (bitonic).

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

Problem

Noah suggests the following card game. You are given a deck of cards, each with a distinct positive integer written on it. The cards are shuffled and placed in a row. Your objective is to arrange the cards in the row so that the values increase monotonically at first and then decrease monotonically for the rest of the sequence.

The only move allowed is to swap two neighboring cards. Cards may swap positions only if they are adjacent to each other.

In the final arrangement, the increasing prefix may be empty, so the whole sequence is in decreasing order. The decreasing suffix may also be empty.

What is the fewest number of moves needed to arrange the cards in the required order?

Input

The first line of input contains a single integer $n$ ( $1 \le n \le 3 \cdot 10^5$ ), the number of cards.

Each of the next $n$ lines contains a single integer $c$ ( $1 \le c \le 10^9$ ). These are the cards, in their initial order. All of them are distinct.

Output

Output a single integer: the fewest number of moves needed to arrange the cards as specified.

Examples1

Example 1
Input
```
8
7
4
8
10
1
2
6
9
```
Expected output
```
7
```