题目描述

译自 JOI 2021 Final T3「集合写真 / Group Photo」

在集训营的最后一天，$N$ 个营员一起照了一张集体照。营员按身高从 $1$ 到 $N$ 编号。营员 $h$ 的身高为 $h\ (1\le h\le N)$。

营员为了拍照而站在台阶上。有 $N$ 级台阶，这 $N$ 级台阶按从低到高的顺序从 $1$ 到 $N$ 编号。

第 $i+1$ 级台阶比第 $i$ 级台阶高 $2\ (1\le i\le N-1)$。因为台阶很窄，所以每级台阶只站一个营员。当营员站成一列后，就开始照集体照。

马上就要拍集体照了。每个台阶都站着一个营员。现在，营员 $H_i$ 站在第 $i$ 级台阶上（$1\le i\le N$）。

然而，因为营员的身高差异太大，如果按这样的站法照相，一些营员就会被前面的营员挡住。所以，你希望改变营员的站位，使得在照片上至少能看到所有营员的脸。换句话说，需要满足以下条件：

• 令站在第 $i\ (1\le i\le N)$ 级台阶的营员身高为 $a_i$。那么对于所有 $i\ (1\le i\le N-1)$，都要满足不等式 $a_i<a_{i+1}+2$。

你只能交换相邻两营员的位置。换句话说，一次操作中，你可以任意选择一个一个台阶 $i\ (1\le i\le N-1)$，然后交换站在台阶 $i$ 与台阶 $i+1$ 上的营员。

你想要最小化交换次数，使得满足以上条件。

给定这些营员目前的顺序，写一个程序计算最小交换次数。

输入格式

第一行一个整数 $N$；

第二行 $N$ 个整数 $H_i$。

输出格式

输出一行一个整数，表示最小交换次数。

5
3 5 2 4 1

3

5
3 2 1 5 4

0

9
6 1 3 4 9 5 7 8 2

9

数据范围与提示

对于所有数据，满足：

• $3\le N\le 5\ 000$；
• $1\le H_i\le N\ (1\le i\le N)$；
• $H_i\neq H_j\ (1\le i<j\le N)$。

详细子任务附加限制及分值如下表所示：