← 返回题目列表

AtCoder · joi2021ho_c

C. 合影

中文机器翻译题面 查看原题

配点: 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).

小課題

  1. (5 点) N \leqq 9.
  2. (7 点) N \leqq 20.
  3. (32 点) N \leqq 200.
  4. (20 点) N \leqq 800.
  5. (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