{"problem":{"name":"[JOI Open 2022] 长颈鹿 / Giraffes","description":{"content":"IOI 动物园以长颈鹿而闻名。IOI 动物园中有 $N$ 只长颈鹿，按身高递增顺序编号为 $1 \\sim N$。长颈鹿的身高两两不同。共有 $N$ 个笼舍排成一排，从左到右编号为 $1 \\sim N$。每个笼舍居住一只长颈鹿。笼舍 $i$ 中居住长颈鹿 $P_i$。 APIO 先生是 IOI 动物园园长。他正担心 IOI 动物园的评级问题。IOI 动物园因“长颈鹿的观感很糟”的原因收到了差评。具","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":7000,"memory_limit":1122304},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8425"},"statements":[{"statement_type":"Markdown","content":"IOI 动物园以长颈鹿而闻名。IOI 动物园中有 $N$ 只长颈鹿，按身高递增顺序编号为 $1 \\sim N$。长颈鹿的身高两两不同。共有 $N$ 个笼舍排成一排，从左到右编号为 $1 \\sim N$。每个笼舍居住一只长颈鹿。笼舍 $i$ 中居住长颈鹿 $P_i$。\n\nAPIO 先生是 IOI 动物园园长。他正担心 IOI 动物园的评级问题。IOI 动物园因“长颈鹿的观感很糟”的原因收到了差评。具体来说，当一个游客和长颈鹿拍照时，游客会选择两个整数 $l, r$（$1 \\le l \\le r \\le N$）并给在笼舍 $l, l + 1, \\ldots, r$ 的长颈鹿拍照。那么，只要下列两个条件**都满足**，这些长颈鹿的观感就是差的。\n\n- 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都高。换句话说，存在一个整数 $k$（$l < k < r$）满足 $P_l < P_k > P_r$。\n- 存在一只长颈鹿，满足这只长颈鹿比两端的长颈鹿都矮。换句话说，存在一个整数 $k$（$l < k < r$）满足 $P_l > P_k < P_r$。\n\nAPIO 先生将重新排列这些长颈鹿，满足对于游客对任意 $l, r$（$1 \\le l \\le r \\le N$）的选择，长颈鹿的观感都不会是差的。因为将一只长颈鹿从一个笼舍挪到另一个笼舍很费功夫，他想要最小化移动长颈鹿的只数。当然，在移动之后，每个笼舍应仍只有一只长颈鹿居住。\n\n给定目前长颈鹿的信息，写一个程序计算最少要移动多少只长颈鹿。因为 APIO 先生目前的长颈鹿排布是随机的，你可以假设 $P_i$（$1 \\le i \\le N$）的值是随机生成的（见【**数据生成**】一节了解详细信息）。\n\n## Input\n\n第一行，一个正整数 $N$。\n\n第二行，$N$ 个正整数 $P_1, P_2, \\ldots, P_N$。\n\n## Output\n\n输出一行一个整数，表示最少要移动多少只长颈鹿。\n\n[samples]\n\n## Background\n\n**译自 [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)。**\n\n## Note\n\n**【样例解释 \\#1】**\n\nIOI 动物园中共有 $6$ 只长颈鹿。长颈鹿 $5,4,6,1,3,2$ 按从左到右的顺序居住在各自的笼舍中。这样排列的话，如果游客对 $l = 2, r = 5$ 的长颈鹿拍照的话，观感就是差的。两个条件按如下方式满足。\n\n- 住在笼舍 $3$ 的长颈鹿比住在最左（笼舍 $2$）和最右（笼舍 $5$）笼舍的长颈鹿都高。\n- 住在笼舍 $4$ 的长颈鹿比住在最左（笼舍 $2$）和最右（笼舍 $5$）笼舍的长颈鹿都矮。\n\n如果 APIO 先生将长颈鹿 $1$ 从笼舍 $4$ 移到笼舍 $1$，然后将长颈鹿 $5$ 从笼舍 $1$ 移动到笼舍 $4$，那么对于游客的任意选择，观感都不会是差的。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。\n\n这组样例满足所有子任务的限制。\n\n----\n\n**【样例解释 \\#2】**\n\nIOI 动物园中共有 $4$ 只长颈鹿。长颈鹿 $4, 1, 3, 2$ 按从左到右的顺序居住在各自的笼舍中。这样排列的话，对于游客的任意选择，观感都不会变差。APIO 先生不需要移动长颈鹿，因此输出 $0$。\n\n这组样例满足所有子任务的限制。\n\n----\n\n**【样例解释 \\#3】**\n\n以 APIO 先生将长颈鹿 $3, 5, 6, 7, 4, 2, 1$ 按从左到右的顺序居住在各自笼舍中为例。对于游客的任意选择，观感都不会变差。APIO 先生通过移动 $2$ 只长颈鹿达成了目标。因为这是移动只数的最小值，所以输出 $2$。\n\n这组样例满足所有子任务的限制。\n\n----\n\n**【样例解释 \\#4】**\n\n这组样例满足子任务 2、3、4 的限制。\n\n----\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n- 子任务 1（10 分）：$N \\le 7$。\n- 子任务 2（22 分）：$N \\le 13$。\n- 子任务 3（27 分）：$N \\le 300$。\n- 子任务 4（41 分）：无特殊限制。\n\n对于所有数据，满足 $1 \\le N \\le 8000$，$1 \\le P_i \\le N$，$P_i$ 两两不同，保证 $P_i$ 是随机生成的（见【**数据生成**】一节了解详细信息）。\n\n----\n\n**【数据生成】**\n\n在本题，除了样例输入，有 $10$ 组数据满足子任务 1、2、3、4 的限制，有 $10$ 组数据满足子任务 2、3、4 的限制，有 $10$ 组数据满足子任务 3、4 的限制，有 $10$ 组数据满足子任务 4 的限制。包括样例，总计有 $44$ 组数据用于评分。所有 $44$ 组数据按如下方式生成：\n\n1. 首先，生成满足子任务的 $N$。\n2. 然后，在 $N! = 1 \\times 2 \\times \\cdots \\times N$ 个满足限制的排列 $(P_1, P_2, \\ldots, P_N)$ 中，等概率随机选择一个作为 $P_1, P_2, \\ldots, P_N$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8425","tags":["2022","O2优化","JOI（日本）"],"sample_group":[["6\n5 4 6 1 3 2\n","2\n"],["4\n4 1 3 2\n","0\n"],["7\n3 1 6 7 4 2 5\n","2\n"],["13\n8 5 6 13 4 2 11 3 9 1 10 7 12\n","6\n"]],"created_at":"2026-03-03 11:09:25"}}