P8425 [JOI Open 2022] 长颈鹿（Giraffes）

**译自 [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T2. [キリン](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/giraffes/2022-open-giraffes-statement.pdf) / [Giraffes](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/giraffes/2022-open-giraffes-statement-en.pdf)。**

IOI 动物园以长颈鹿而闻名。IOI 动物园中有 $N$ 只长颈鹿，按身高递增顺序编号为 $1 \sim N$。长颈鹿的身高两两不同。共有 $N$ 个笼舍排成一排，从左到右编号为 $1 \sim N$。每个笼舍居住一只长颈鹿。笼舍 $i$ 中居住长颈鹿 $P_i$。 APIO 先生是 IOI 动物园园长。他正担心 IOI 动物园的评级问题。IOI 动物园因“长颈鹿的观感很糟”的原因收到了差评。具体来说，当一个游客和长颈鹿拍照时，游客会选择两个整数 $l, r$（$1 \le l \le r \le N$）并给在笼舍 $l, l + 1, \ldots, r$ 的长颈鹿拍照。那么，只要下列两个条件**都满足**，这些长颈鹿的观感就是差的。 - 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都高。换句话说，存在一个整数 $k$（$l < k < r$）满足 $P_l < P_k > P_r$。 - 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都矮。换句话说，存在一个整数 $k$（$l < k < r$）满足 $P_l > P_k < P_r$。 APIO 先生将重新排列这些长颈鹿，满足对于游客对任意 $l, r$（$1 \le l \le r \le N$）的选择，长颈鹿的观感都不会是差的。因为将一只长颈鹿从一个笼舍挪到另一个笼舍很费功夫，他想要最小化移动长颈鹿的只数。当然，在移动之后，每个笼舍应仍只有一只长颈鹿居住。 给定目前长颈鹿的信息，写一个程序计算最少要移动多少只长颈鹿。因为 APIO 先生目前的长颈鹿排布是随机的，你可以假设 $P_i$（$1 \le i \le N$）的值是随机生成的（见【**数据生成**】一节了解详细信息）。

无

无

**【样例解释 \#1】** IOI 动物园中共有 $6$ 只长颈鹿。长颈鹿 $5,4,6,1,3,2$ 按从左到右的顺序居住在各自的笼舍中。这样排列的话，如果游客对 $l = 2, r = 5$ 的长颈鹿拍照的话，观感就是差的。两个条件按如下方式满足。 - 住在笼舍 $3$ 的长颈鹿比住在最左（笼舍 $2$）和最右（笼舍 $5$）笼舍的长颈鹿都高。 - 住在笼舍 $4$ 的长颈鹿比住在最左（笼舍 $2$）和最右（笼舍 $5$）笼舍的长颈鹿都矮。 如果 APIO 先生将长颈鹿 $1$ 从笼舍 $4$ 移到笼舍 $1$，然后将长颈鹿 $5$ 从笼舍 $1$ 移动到笼舍 $4$，那么对于游客的任意选择，观感都不会是差的。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。 这组样例满足所有子任务的限制。 ---- **【样例解释 \#2】** IOI 动物园中共有 $4$ 只长颈鹿。长颈鹿 $4, 1, 3, 2$ 按从左到右的顺序居住在各自的笼舍中。这样排列的话，对于游客的任意选择，观感都不会变差。APIO 先生不需要移动长颈鹿，因此输出 $0$。 这组样例满足所有子任务的限制。 ---- **【样例解释 \#3】** 以 APIO 先生将长颈鹿 $3, 5, 6, 7, 4, 2, 1$ 按从左到右的顺序居住在各自笼舍中为例。对于游客的任意选择，观感都不会变差。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。 这组样例满足所有子任务的限制。 ---- **【样例解释 \#4】** 这组样例满足子任务 2、3、4 的限制。 ---- **【数据范围】** **本题采用捆绑测试。** - 子任务 1（10 分）：$N \le 7$。 - 子任务 2（22 分）：$N \le 13$。 - 子任务 3（27 分）：$N \le 300$。 - 子任务 4（41 分）：无特殊限制。 对于所有数据，满足 $1 \le N \le 8000$，$1 \le P_i \le N$，$P_i$ 两两不同，保证 $P_i$ 是随机生成的（见【**数据生成**】一节了解详细信息）。 ---- **【数据生成】** 在本题，除了样例输入，有 $10$ 组数据满足子任务 1、2、3、4 的限制，有 $10$ 组数据满足子任务 2、3、4 的限制，有 $10$ 组数据满足子任务 3、4 的限制，有 $10$ 组数据满足子任务 4 的限制。包括样例，总计有 $44$ 组数据用于评分。所有 $44$ 组数据按如下方式生成： 1. 首先，生成满足子任务的 $N$。 2. 然后，在 $N! = 1 \times 2 \times \cdots \times N$ 个满足限制的排列 $(P_1, P_2, \ldots, P_N)$ 中，等概率随机选择一个作为 $P_1, P_2, \ldots, P_N$。