問題文

$N$ 項からなる非負整数列 $A = (A_1, A_2, \dots, A_N)$ があります。 すべての $i = 1, 2, \dots, N$ に対して $A_i = 0$ となるまで、高橋君は以下の操作を繰り返し行います。

操作：

• $i = 1, 2, \dots, N$ のうち、$A_i > 0$ を満たす最小の $i$ を $j$ とする。このときの $A_j$ の値を $K$ とする。
• $i = j, j+1, \dots, N$ それぞれに対して、$A_i \geq K$ であれば $A_i$ を $A_i-K$ に置き換える。そうでなければ何もしない。

この操作は有限回で終了することが証明できます。高橋君が操作を行う回数を求めてください。

入力

$N$
$A_1\ A_2 \dots A_N$

• 入力は全て整数
• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 2 \times 10^5$

出力

答えを一行に出力してください。

サンプル

3
3 1 4

2

1
0

0

17
1 0 54 21 87 79 79 82 12 28 41 2 53 26 22 80 19

10