配点: 100 点
某训练营最后一天,该训练营的学员 N 我们决定拍一张合影。参与者按照身高顺序排列。 它们的编号最大为 1 它们的编号最大为 N 。参与者 h 的高度是 h (1 \leqq h \leqq N).
集体照是在楼梯上排队拍摄的。这个楼梯只是 N 由阶段组成,从最低的开始 它们的编号最大为 1 它们的编号最大为 N 。步骤 i + 1 是一个步骤 刚刚超过 i 仅仅超过 2 更高(1 \leqq i \leqq N - 1).楼梯的宽度很窄,所以每个台阶上都有很多参与者。 1 每个人垂直站立并拍照。
摄影即将开始,参与者站在每一个台阶上。目前,阶段 i (1 \leqq i \leqq N) H_i 。
不过,由于参加者的身高相差太大,部分参加者可能不会按此顺序出现在照片中。因此,您想要重新排列参与者的位置,以便至少每个人的头顶都是可见的。换句话说,我们要确保满足以下条件。
- 段 i (1 \leqq i \leqq N) a_i 。 此时,所有 i (1 \leqq i \leqq N - 1),a_{i} < a_{i + 1} + 2 成立。
但是,您只能交换相邻参与者的位置。也就是说, 在1 操作中,阶段 i (1 \leqq i \leqq N - 1) 任意选择并且 i 参与者和阶段 您可以替换 i + 1 中的参与者。
我们希望尽可能少地执行此操作,以确保满足条件。
给定当前参与者的顺序,编写一个程序来查找所需的最少操作数。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N H_1 \cdots H_N
出力
所需的最少操作数被发送到标准输出。 1 行。 在
制約
- 3 \leqq N \leqq 5\,000.
- 1 \leqq H_i \leqq N (1 \leqq i \leqq N).
- H_i \neq H_j (1 \leqq i < j \leqq N).
小課題
- (5 点) N \leqq 9.
- (7 点) N \leqq 20.
- (32 点) N \leqq 200.
- (20 点) N \leqq 800.
- (36 点)没有额外的限制。
入力例 1
5 3 5 2 4 1
出力例 1
3
操作如下。 通过执行此 3 次,可以满足条件。
- 一、步骤 交换 2 参与者和阶段 您可以替换 3 中的参与者。参与者的身高按从前到后的顺序列出。 3, 2, 5, 4, 1 变为。
- 下一步 4 参与者和阶段 您可以替换 5 中的参与者。参与者的身高按从前到后的顺序列出。 3, 2, 5, 1, 4 变为。
- 最后,舞台 3 参与者和阶段 您可以替换 4 中的参与者。参与者的身高按从前到后的顺序列出。 3, 2, 1, 5, 4 ,满足条件。
2 不可能用较少的操作来满足条件,所以 输出3 。
入力例 2
5 3 2 1 5 4
出力例 2
0
由于条件已满足,因此无需执行任何操作。
入力例 3
9 6 1 3 4 9 5 7 8 2
出力例 3
9