在训练营结束时，将为 $N$ 名参与者拍摄合影。参与者按身高从 $1$ 到 $N$ 编号。身高为 $h$ 的参与者其编号即为 $h$ ($1 \le h \le N$)。

参与者站在楼梯上拍照。楼梯共有 $N$ 级台阶。台阶从低到高编号为 $1$ 到 $N$。

第 $i+1$ 级台阶比第 $i$ 级台阶高 $2$ ($1 \le i \le N-1$)。由于楼梯狭窄，每级台阶上只能站一名参与者。当参与者排成一列时，将拍摄合影。

合影即将开始。每级台阶上站着一名参与者。目前，参与者 $H_i$ 站在第 $i$ 级台阶上 ($1 \le i \le N$)。

然而，由于参与者之间的身高差过大，如果按当前的顺序拍照，一些参与者可能会被其他参与者遮挡。因此，你希望改变参与者的顺序，使得至少每位参与者的头部都能在照片中显示出来。换句话说，需要满足以下条件：

• 设 $a_i$ 为站在第 $i$ 级台阶上的参与者的身高 ($1 \le i \le N$)。则对于每一个 $i$ ($1 \le i \le N-1$)，不等式 $a_i < a_{i+1} + 2$ 均成立。

你只能交换相邻的参与者。换句话说，通过一次操作，你可以任意选择一个台阶 $i$ ($1 \le i \le N-1$)，并交换站在第 $i$ 级台阶和第 $i+1$ 级台阶上的参与者。

你希望在满足上述条件的前提下，使操作次数最少。

编写一个程序，在给定参与者初始顺序的情况下，计算所需的最少操作次数。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N$ $H_1 \dots H_N$

输出格式

将结果输出到标准输出。输出应包含最少操作次数。

数据范围

• $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$)。

子任务

1. (5 分) $N \le 9$。
2. (7 分) $N \le 20$。
3. (32 分) $N \le 200$。
4. (20 分) $N \le 800$。
5. (36 分) 无附加限制。

样例

样例输入 1

5
3 5 2 4 1

样例输出 1

3

说明 1

如果执行以下三次操作，条件即可满足：

• 首先，交换第 2 级和第 3 级台阶上的参与者。从低到高，参与者的身高变为 3, 2, 5, 4, 1。
• 其次，交换第 4 级和第 5 级台阶上的参与者。从低到高，参与者的身高变为 3, 2, 5, 1, 4。
• 最后，交换第 3 级和第 4 级台阶上的参与者。从低到高，参与者的身高变为 3, 2, 1, 5, 4。此时条件满足。

由于执行少于三次操作无法满足条件，因此输出 3。

样例输入 2

5
3 2 1 5 4

样例输出 2

0

说明 2

条件已经满足。你不需要进行任何操作。

样例输入 3

9
6 1 3 4 9 5 7 8 2

样例输出 3

9