2020 South Central USA Regional Contest

#### Start

2021-03-06 10:00 AKST

## 2020 South Central USA Regional Contest

#### End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -103 days 20:00:26

5:00:00

0:00:00

# Problem CBitonic Ordering

Noah suggests the following card game: You are given a deck of cards, each with a distinct positive integer value 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 are monotonically increasing initially, and then monotonically decreasing for the remainder of the sequence.

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

Note that in the final ordered sequence, the initial increasing portion of the sequence may be empty (such that the whole sequence is in descending order). Likewise it is allowed for the decreasing portion of the sequence to be empty.

What is the fewest number of moves needed to get the cards arranged in the proper order?

## Input

The first line of input contains a single integer $n$ ($1 \leq n \leq 3\cdot 10^5$), which is 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. They will all be distinct.

## Output

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

Sample Input 1 Sample Output 1
8
7
4
8
10
1
2
6
9

7