{"problem":{"name":"[HUSTFC 2023] 排列排序问题","description":{"content":"JokerShaco 有一个长度为 $n$ 的排列 $p$，他认为一个排列必须是有序的，所以他打算将其进行排序。 他可以对这个排列进行如下操作： - 将这个排列切割成若干个序列（也可以不切割，保持原样），每个序列至少含有一个元素； - 选择其中一些序列并将它们翻转； - 将这些序列按照他的意愿重新组合拼接得到一个新的排列。 JokerShaco 认为切割操作非常累，他想知道如果必须把这个排列变","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9771"},"statements":[{"statement_type":"Markdown","content":"JokerShaco 有一个长度为 $n$ 的排列 $p$，他认为一个排列必须是有序的，所以他打算将其进行排序。\n\n他可以对这个排列进行如下操作：\n- 将这个排列切割成若干个序列（也可以不切割，保持原样），每个序列至少含有一个元素；\n- 选择其中一些序列并将它们翻转；\n- 将这些序列按照他的意愿重新组合拼接得到一个新的排列。\n\nJokerShaco 认为切割操作非常累，他想知道如果必须把这个排列变得有序，至少需要切割多少次。\n\n一个长度为 $n$ 的排列的定义为，包含从 $1$ 到 $n$ 这 $n$ 个不同的整数的序列，每个整数恰好出现一次。\n\n序列翻转的定义为，假设存在一个长度为 $m$ 的序列 $[a_1,a_2,\\dots,a_{m-1},a_m]$，那么将这个序列翻转后将会得到 $[a_m,a_{m-1},\\dots,a_2,a_1]$。\n\n## Input\n\n第一行包含一个整数 $n\\ (1\\le n\\le 10^6$)，表示排列 $p$ 的长度。\n\n第二行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $p_i$。保证输入的 $p$ 一定是长度为 $n$ 的排列。\n\n## Output\n\n输出一个整数，表示将排列 $p$ 变得有序所需的最少切割次数。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9771","tags":["2023","O2优化","高校校赛"],"sample_group":[["5\n1 2 3 5 4\n","1\n"],["3\n3 2 1\n","0\n"]],"created_at":"2026-03-03 11:09:25"}}