問題文

小星さんは誕生日プレゼントとして長さ $N$ の数列 $A_1,A_2,\ldots,A_N$ をもらいました。小星さんはこの数列を昇順にソートしようと思っています。

ある店では長さ $N$ の数列に操作を行う道具が $N-1$ 種類売られています。$i=2,3,\ldots,N$ に対し、道具 $i$ は長さ $N$ の数列 $B_1,B_2,\ldots,B_N$ に次のような操作を行います。

• 先頭 $i$ 項に巡回シフトを行う。すなわち、$B_1,B_2,\ldots,B_i,B_{i+1},\ldots,B_N$ を $B_2,\ldots,B_i,B_1,B_{i+1},\ldots,B_N$ に変更する。

小星さんはこの店で道具を $0$ 種類以上買おうとしています。買った道具は何回でも使うことができます。

数列 $A_1,A_2,\ldots,A_N$ を昇順にソートするには少なくとも何種類の道具が必要でしょうか。

入力

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

• 入力はすべて整数
• $2\le N\le 2\times 10^5$
• $1\le A_i\le 10^9$

出力

数列を昇順にソートするには少なくとも何種類の道具が必要かを求め、出力してください。

サンプル

5
3 4 1 6 7

1

6
5 3 1 2 4 6

2

4
1 1 2 3

0