题目描述

$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,\dots,\ p_n,\ p_1$ に並び替える。

順列を昇順に並び替えるのに必要な操作回数の最小値を求めてください。 ただし、与えられる入力について、これらの操作によって順列を昇順に並び替えられることが保証されています。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

順列を昇順に並び替えるのに必要な操作回数の最小値を出力せよ。

题目大意

给定一个 $1\sim n$ 的排列 $a$，每次可以对其进行下面两种操作的其中之一：

1. 取反整个数列，即 $\{a_1,a_2,\cdots,a_n\}\rightarrow\{a_n,a_{n-1},\cdots,a_1\}$。
2. 将第一个数挪到最后面，即 $\{a_1,a_2,\cdots,a_n\}\rightarrow\{a_2,a_3,\cdots,a_n,a_1\}$。

问若要将 $a$ 变成 $\{1,2,\cdots,n\}$，至少需要多少次操作。数据保证有解。

3
1 3 2

2

2
2 1

1

10
2 3 4 5 6 7 8 9 10 1

3

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

0

提示

制約

• $2\ \leq\ n\ \leq\ 10^5$
• $p_1,\dots,p_n$ は $1,\dots,n$ の順列
• 問題文中の操作によって $p_1,\dots,p_n$ を昇順に並び替えられる

Sample Explanation 1

次のように操作すると $2$ 回で昇順に並び替えできます。 1. 先頭の項を末尾に移動させ、 $3,\ 2,\ 1$ に並び替える。 2. 全体をひっくりかえし、$1,\ 2,\ 3$ に並び替える。 $2$ 回未満の操作で昇順に並び替えることはできないため、答えは $2$ です。

Sample Explanation 2

どちらの操作をしても $1$ 回で昇順に並び替えできます。 $1$ 回未満の操作で昇順に並び替えることはできないため、答えは $1$ です。

Sample Explanation 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$ です。

Sample Explanation 4

一度も操作する必要がありません。