桌上排成一排摆放着几张写有数字的卡片。

我们希望改变它们的顺序，使得前一部分卡片上的数字呈非递减顺序，其余部分呈非递增顺序。例如，$(1, 2, 3, 2, 1)$、$(1, 1, 3, 4, 5, 9, 2)$ 和 $(5, 3, 1)$ 是可以接受的顺序，而 $(8, 7, 9)$ 和 $(5, 3, 5, 3)$ 则不是。

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

在重排过程中，每次只允许交换相邻两张卡片的位置。我们想要知道完成重排所需的最少交换次数。

输入格式

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

$n$ $a_1 \dots a_n$

第一行是一个整数 $n$，表示卡片的数量（$1 \le n \le 100\,000$）。第二行是 $n$ 个整数 $a_1$ 到 $a_n$，表示卡片上印有的数字，按其原始位置排列（$1 \le a_i \le 100\,000$）。

输出格式

输出一行，表示按指定要求重排卡片所需的最少交换次数。

样例

样例输入 1

7
3 1 4 1 5 9 2

样例输出 1

3

样例输入 2

9
10 4 6 3 15 9 1 1 12

样例输出 2

8

样例输入 3

8
9 9 8 8 7 7 6 6

样例输出 3

0

样例输入 4

6
8 7 2 5 4 6

样例输出 4

4