Deque

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$ and an empty deque.

You must insert the numbers of the sequence into the deque one by one, in order. For each number you may choose to push it to the front or to the back of the deque.

Minimize the number of inversions in the final sequence obtained from the deque.

Input Format

The first line contains an integer $n$, the length of the sequence ($1 \le n \le 2 \times 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, the given sequence ($-10^9 \le a_i \le 10^9$).

Output Format

Output one integer on a single line: the minimum possible number of inversions.

Sample Input

4
3 7 5 5

Sample Output

2