配点 : $400$ 点

問題文

$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$ に並び替える。

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

制約

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

入力

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

$n$

$p_1$ $\dots$ $p_n$

出力

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

3
1 3 2

2

次のように操作すると $2$ 回で昇順に並び替えできます。

1. 先頭の項を末尾に移動させ、 $3, 2, 1$ に並び替える。
2. 全体をひっくりかえし、$1, 2, 3$ に並び替える。

$2$ 回未満の操作で昇順に並び替えることはできないため、答えは $2$ です。

2
2 1

1

どちらの操作をしても $1$ 回で昇順に並び替えできます。

$1$ 回未満の操作で昇順に並び替えることはできないため、答えは $1$ です。

10
2 3 4 5 6 7 8 9 10 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$ です。

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

0

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