该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3470.zip](file://AdditionalFile3470.zip?type=additional_file)

P7406 [JOI 2021 Final] 集体照 / Group Photo

题目描述

有 $N$ 个人，这 $N$ 个人编号为 $1 \sim N$，第 $h$ 个人的身高为 $h$。

有 $N$ 个台阶，这 $N$ 个台阶从低到高编号为 $1 \sim N$，第 $i$ 级台阶比第 $i+1$ 个台阶低 $2$ 个单位高度。每个台阶上只能站一个人，第 $H_i$ 个人站在第 $i$ 个台阶上。

你可以进行无数次如下操作：

• 选择 $i \in [1,N-1]$，交换第 $i$ 个台阶上的人和第 $i+1$ 个台阶上的人。

假设第 $i$ 个台阶上站的人的高度为 $a_i$，你要满足：

• 对于任意 $i \in [1,N-1]$，都有 $a_i <a_{i+1}+2$。

求最少的操作次数。

输入格式

第一行一个整数 $N$ 代表人数。

第二行 $N$ 个整数 $H_i$ 代表第 $H_i$ 个人站在第 $i$ 个台阶上。

输出格式

一行一个整数代表最少的操作次数。

输入输出样例 #1

输入 #1

5
3 5 2 4 1

输出 #1

3

输入输出样例 #2

输入 #2

5
3 2 1 5 4

输出 #2

0

输入输出样例 #3

输入 #3

9
6 1 3 4 9 5 7 8 2

输出 #3

9

说明/提示

样例 1 解释

设 $h_i$ 为第 $i$ 个台阶上站的人的身高：

• 交换第 $2$ 个人和第 $3$ 个人，$h_i=\{3,2,5,4,1\}$。
• 交换第 $4$ 个人和第 $5$ 个人，$h_i=\{3,2,5,1,4\}$。
• 交换第 $3$ 个人和第 $4$ 个人，$h_i=\{3,2,1,5,4\}$。

$3$ 步刚好满足要求。

样例 2 解释

已经满足要求，不需要进行任何操作。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$N \le 9$。
• Subtask 2（7 pts）：$N \le 20$。
• Subtask 3（32 pts）：$N \le 200$。
• Subtask 4（20 pts）：$N \le 800$。
• Subtask 5（36 pts）：无特殊限制。

对于 $100\%$ 的数据，$3 \le N \le 5000$，$1 \le H_i \le N$，$H_i$ 互不相等。

说明

翻译自 The 20th Japanese Olympiad in Informatics Final Round C 集合写真的英文翻译 Group Photo。

#3470. 「JOI 2021 Final」集体照

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

译自 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$。

输出格式

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

样例 1

输入

5
3 5 2 4 1

输出

3

你可以按如下三步交换，使得满足条件：

• 首先，交换站在台阶 $2$ 和 $3$ 的营员。交换后按台阶从低到高的顺序，站的营员身高为 $3,2,5,4,1$。
• 第二步，交换站在台阶 $4$ 和 $5$ 的营员。交换后按台阶从低到高的顺序，站的营员身高为 $3,2,5,1,4$。
• 最后，交换站在台阶 $3$ 和 $4$ 的营员。交换后按台阶从低到高的顺序，站的营员身高为 $3,2,1,5,4$。上述条件满足。

因为操作小于 $3$ 次无法满足条件，因此输出 $3$。

样例 2

输入

5
3 2 1 5 4

输出

0

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

样例 3

输入

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

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