题目背景
译自 Natjecanje timova studenata informatičara hrvatskih sveučilišta D.
题目描述
给定 1∼n 的排列 p1,p2,…,pn。
你可以执行任意多次(包括零次)以下操作:
- 将 p 划分成可以为空的四段,依次记为 a,b,c,d。将这四段重排成 c,a,d,b。
求出至少操作多少次后,排列将变为 1,2,…,n。
输入格式
第一行,一个正整数 n。
第二行,n 个正整数 p1,p2,…,pn。
输出格式
输出一行一个非负整数,表示答案。
9
3 4 7 8 9 1 2 5 6
1
3
1 3 2
1
4
1 3 2 4
2
提示
样例解释
- 样例 1 解释:
- 令 a=[3,4],b=[7,8,9],c=[1,2],d=[5,6]。
- 交换后变为 [1,2],[3,4],[5,6],[7,8,9]。
- 样例 2 解释:
- 令 a=[1],b=[3],c=[],d=[2]。
- 交换后变为 [],[1],[2],[3]。
数据范围
- 1≤n≤10。