#P18851. [Croatian CPC2024] Drevni Diskovi
[Croatian CPC2024] Drevni Diskovi
Drevni Diskovi
题目描述
Malnar 找到了安装 Windows 95 所用的一组旧软盘。它们按照安装时的使用顺序编号为 到 。他希望将目前排成一行的软盘按编号从小到大排序。
他只能进行一种操作:
- 将整个序列划分为四个连续段,依次记为 。每段可以为空。
- 将这四段重新排列为 ,每段内部的顺序保持不变。
不同操作可以采用不同的划分。求将给定排列变为 所需的最少操作次数。
输入格式
第一行包含整数 ()。
第二行包含 到 的一个排列,表示软盘的初始顺序。
输出格式
输出一个整数,表示最少操作次数。
样例输入 1
9
3 4 7 8 9 1 2 5 6
样例输出 1
1
样例输入 2
3
1 3 2
样例输出 2
1
样例输入 3
4
1 3 2 4
样例输出 3
2
样例解释
第一个样例可以划分为 、、、,一次操作后即为升序。

第二个样例可以划分为 、、、,一次操作后变为 。
