#P18851. [Croatian CPC2024] Drevni Diskovi

[Croatian CPC2024] Drevni Diskovi

Drevni Diskovi

题目描述

Malnar 找到了安装 Windows 95 所用的一组旧软盘。它们按照安装时的使用顺序编号为 11 到 nn。他希望将目前排成一行的软盘按编号从小到大排序。

他只能进行一种操作:

  1. 将整个序列划分为四个连续段,依次记为 A,B,C,DA,B,C,D。每段可以为空。
  2. 将这四段重新排列为 C,A,D,BC,A,D,B,每段内部的顺序保持不变。

不同操作可以采用不同的划分。求将给定排列变为 1,2,…,n1,2,\ldots,n 所需的最少操作次数。

输入格式

第一行包含整数 nn(1≤n≤101\le n\le10)。

第二行包含 11 到 nn 的一个排列,表示软盘的初始顺序。

输出格式

输出一个整数,表示最少操作次数。

样例输入 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

样例解释

第一个样例可以划分为 A=(3,4)A=(3,4)、B=(7,8,9)B=(7,8,9)、C=(1,2)C=(1,2)、D=(5,6)D=(5,6),一次操作后即为升序。

第一个样例

第二个样例可以划分为 A=(1)A=(1)、B=(3)B=(3)、C=∅C=\varnothing、D=(2)D=(2),一次操作后变为 (1,2,3)(1,2,3)。

第二个样例