题目描述

给定一个长度为 $N$ 的排列 $P=(P_1, P_2, \cdots, P_N)$。我们希望通过若干次相邻元素交换，使排列 $P$ 满足下面的条件：

• 在所有 $i$ 中，满足 $P_i > P_{i+1}$ 的 $i$ 的数量最多为 1 个。

请找出使 $P$ 满足条件所需的最小交换次数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $P_1$ $P_2$ $\cdots$ $P_N$

输出格式

输出结果所需的交换次数。

输入输出样例 #1

输入 #1

3
3 2 1

输出 #1

1

输入输出样例 #2

输入 #2

4
2 4 1 3

输出 #2

0

输入输出样例 #3

输入 #3

6
2 3 1 6 4 5

输出 #3

1

输入输出样例 #4

输入 #4

20
8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9

输出 #4

36

说明/提示

• $2 \leq N \leq 800000$
• $(P_1, P_2, \cdots, P_N)$ 是 $(1, 2, \cdots, N)$ 的一个排列
• 输入的所有值均为整数

样例说明

通过交换 $P_1$ 和 $P_2$，可以将 $P$ 变为 $(2, 3, 1)$，此时排列满足条件。