問題
$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 \ $が条件を満たす最大の値となる。