数列のソート 4

長さ $N$ の数列 $A$ が整列されているとは、すべての $1 \leq i < N$ に対して $A_i \leq A_{i+1}$ が成り立つことをいう。

次の操作を $0$ 回以上行える。$1 \leq k \leq N$ を満たす整数 $k$ を選び、$A_k$ に を加え、それ以外のすべての要素から を引く。

操作中や操作後に要素が負になってもよい。どの数列もこの操作で整列できる。整列に必要な操作回数の最小値を求めよ。

入力は次の形式で与えられる。

$N$ $A_1\ A_2\ \cdots\ A_N$

最小操作回数を出力せよ。

• $1 \leq N \leq 100\,000$.
• $0\leq A_i\leq10^9$ ().