問題文

長さ $N$ の数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。

あなたは以下の操作を操作を $0$ 回以上の任意の回数行うことができます。この操作において、 $A_{N+1}$ は $A_1$ を指すものとします。

• $A_i < A_{i+1}$ を満たす整数 $i\ (1 \le i \le N)$ を選択し、以下のいずれかを適用する。
• $A_i$ を $A_{i+1}$ で置き換える
• $A_{i+1}$ を $A_i$ で置き換える

数列 $A$ のすべての要素を等しくするために必要な操作回数の最小値を求めてください。

なお、有限回の操作ですべての要素を等しくできることが示せます。

入力

$N$
$A_1\ A_2\ \dots \ A_N$

• 入力はすべて整数である
• $1 \le N \le 3 \times 10^5$
• $1 \le A_i \le N$

出力

必要な操作回数の最小値を出力してください。 最後に改行してください。

サンプル

3
2 3 1

2

5
1 5 3 3 3

3