004 - Permutation Sort

問題

$1 \ $から$ \ N \ $までの整数を並び替えた数列$ \ A = (a_1,a_2,\ldots,a_N) \ $が与えられます。
以下の条件を満たすような整数$ \ L \ $の最大値を求めてください。

• $(1 \leq L \lt N) \ $を満たす。
• 「$(1 \leq k+L \leq N) \ $を満たすように整数$ \ k \ $を選び、$a_k \ $と$ \ a_{k + L} \ $の値を入れ替える」 という操作を任意の回数(0回でもよい)行ったとき、数列$ \ A \ $を昇順に並べ替えることができる。

なお、条件を満たす整数$ \ L \ $は必ず存在することが示せる。

入力

$N$
$a_1 \ a_2 \ldots a_N$

出力

整数$ \ L \ $の最大値を出力せよ。
出力の末尾には改行を入れること。

制約

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq a_i \leq N \ (1 \leq i \leq N)$
• $a_i \neq a_j \ (i \neq j)$
• 入力は全て整数。

入出力例

入力例１

5
3 4 1 2 5

出力例１

2

$L = 2 \ $とすれば以下のように操作を行うことで$ \ A \ $を昇順に並べ替えることができる。

• $a_1 \ $と$ \ a_3 \ $の値を入れ替える。このとき$ \ A = (1,4,3,2,5) \ $となる。
• $a_2 \ $と$ \ a_4 \ $の値を入れ替える。このとき$ \ A = (1,2,3,4,5) \ $となる。

$L = 1 \ $のときも条件を満たすが、$L \ $の最大値は$ \ 2 \ $となるため$ \ 2 \ $を出力する。

入力例２

4
1 2 3 4

出力例２

3

最初から昇順に並べられているため操作を行う必要はない。よって$ \ L = 3 \ $が条件を満たす最大の値となる。