Xiao D has a sequence $(a_i)_{i=0}^{n-1}$ of length $n$.
Xiao D can swap any two adjacent elements in the sequence at a cost of $1$. Xiao D wants to make the sequence unimodal with the minimum possible cost.
A sequence is defined as unimodal if there exists a $k \in [0, n)$ such that: 1. $\forall 0 \le i < k, a_i \le a_{i+1}$ 2. $\forall k < i < n, a_i \le a_{i-1}$
You need to find this minimum cost.
Input
The first line contains an integer $n$, representing the length of the sequence. The second line contains $n$ integers, representing the elements of the sequence.
Output
Output the minimum cost to make the sequence unimodal.
Examples
Input 1
4 1 2 1 3
Output 1
1
Note 1
One swap is sufficient to make the sequence $(1, 2, 3, 1)$.
Input 2
10 5 6 8 9 4 7 1 5 4 1
Output 2
4
Note 2
The sequence becomes $(5, 6, 8, 9, 7, 5, 4, 4, 1, 1)$.
Subtasks
| Subtask ID | $n \le$ | Special Property | Score |
|---|---|---|---|
| 1 | $10$ | None | $1$ |
| 2 | $100$ | None | $21$ |
| 3 | $10^6$ | $a_i$ are distinct | $36$ |
| 4 | $10^6$ | None | $42$ |
For all data, it is guaranteed that $1 \le n \le 10^6$ and $1 \le a_i \le n$.