题目背景

译自 Natjecanje timova studenata informatičara hrvatskih sveučilišta D.

题目描述

给定 $1\sim n$ 的排列 $p_1,p_2,\ldots,p_n$。

你可以执行任意多次（包括零次）以下操作：

• 将 $p$ 划分成可以为空的四段，依次记为 $a,b,c,d$。将这四段重排成 $c,a,d,b$。

求出至少操作多少次后，排列将变为 $1,2,\ldots,n$。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个正整数 $p_1,p_2,\ldots,p_n$。

输出格式

输出一行一个非负整数，表示答案。

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\le n\le 10$。