Description

几张印有数字的卡片在桌子上排成一列。

我们想要改变它们的顺序，使得一部分卡片按上面数字的非递减顺序排列，其余部分按非递增顺序排列。例如，$(1, 2, 3, 2, 1)$、$(1, 1, 3, 4, 5, 9, 2)$ 和 $(5, 3, 1)$ 是可接受的顺序，但 $(8, 7, 9)$ 和 $(5, 3, 5, 3)$ 则不是。

形式化地说，设 $n$ 为卡片数量，重新排序后第 $i$ 个位置（$1 \leq i \leq n$）卡片上的数字为 $b_i$，应存在 $k \in \{1, \ldots, n\}$，使得 ($b_i \leq b_{i+1} \; \forall i \in \{1, \ldots, k-1\}$) 且 ($b_i \geq b_{i+1} \; \forall i \in \{k, \ldots, n-1\}$) 成立。

为了重新排序，每次只允许交换相邻两张卡片的位置。我们想知道完成重新排序所需的最小交换次数。

Input Format

输入包含单个测试用例，格式如下。

$$\begin{aligned} &n\\ &a_1 \; \ldots \; a_n\\ \end{aligned}$$

第一行的整数 $n$ 是卡片的数量（$1 \leq n \leq 100\,000$）。第二行的整数 $a_1$ 到 $a_n$ 是卡片上印着的数字，按它们原始位置的顺序给出（$1 \leq a_i \leq 100\,000$）。

Output Format

在一行中输出将卡片按指定要求重新排序所需的最小交换次数。

7
3 1 4 1 5 9 2

3

9
10 4 6 3 15 9 1 1 12

8

8
9 9 8 8 7 7 6 6

0

6
8 7 2 5 4 6

4