题目描述

给定一个 $1,\dots,n$ 的排列 $p_1,\dots,p_n$。你可以对该排列进行如下两种操作，操作次数不限、顺序任意：

• 将整个排列翻转。即，将 $p_1,p_2,\dots,p_n$ 变为 $p_n,p_{n-1},\dots,p_1$。
• 将首项移动到末尾。即，将 $p_1,p_2,\dots,p_n$ 变为 $p_2,p_3,\dots,p_n,p_1$。

请你求出将该排列变为升序排列所需的最小操作次数。保证对于给定的输入，使用上述操作一定可以将排列变为升序排列。

输入格式

输入从标准输入读入，格式如下：

$n$ $p_1$ $p_2$ $\dots$ $p_n$

输出格式

输出将排列变为升序排列所需的最小操作次数。

样例 1

输入

3
1 3 2

输出

2

样例 2

输入

2
2 1

输出

1

样例 3

输入

10
2 3 4 5 6 7 8 9 10 1

输出

3

样例 4

输入

12
1 2 3 4 5 6 7 8 9 10 11 12

输出

0

说明/提示

限制条件

• $2 \leq n \leq 10^5$
• $p_1,p_2,\dots,p_n$ 是 $1,\dots,n$ 的一个排列
• 保证通过题目描述的操作一定可以将 $p_1,\dots,p_n$ 变为升序排列

样例解释 1

可以按如下方式用 $2$ 次操作将排列变为升序排列：

1. 将首项移动到末尾，排列变为 $3,2,1$。
2. 将整个排列翻转，排列变为 $1,2,3$。 无法在少于 $2$ 次操作内完成，因此答案为 $2$。

样例解释 2

无论使用哪种操作，只需 $1$ 次即可将排列变为升序排列。无法在少于 $1$ 次操作内完成，因此答案为 $1$。

样例解释 3

可以按如下方式用 $3$ 次操作将排列变为升序排列：

1. 将整个排列翻转，排列变为 $1,10,9,8,7,6,5,4,3,2$。
2. 将首项移动到末尾，排列变为 $10,9,8,7,6,5,4,3,2,1$。
3. 将整个排列翻转，排列变为 $1,2,3,4,5,6,7,8,9,10$。 无法在少于 $3$ 次操作内完成，因此答案为 $3$。

样例解释 4

无需进行任何操作。

由 ChatGPT 4.1 翻译