配点 : $700$ 点

問題文

$N$ 個の文字列が一列に並んでおり、どの隣り合う $2$ つの文字列に対しても、 左に書いてある文字列の方が右に書いてある文字列よりも辞書順で小さいことが分かっています。 つまり、左から $i$ 番目の文字列を $S_i$ としたときに、辞書順で $S_1 が成り立っています。

$S_i$ の長さが $A_i$ であると分かっているとき、$S_1,S_2,...,S_N$ に含まれる文字の種類数として考えられる最小の値を求めてください。

制約

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $A_i$ は整数

Note

文字列は英字アルファベットからなる必要はない。無限に多くの文字があり、辞書式順序がそれらについて定まっているとして良い。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ ... $A_N$

出力

いずれかの文字列に含まれる文字の種類数として考えられる最小の値を出力せよ。

3
3 2 1

2

例えば、$S_1=$abc, $S_2=$bb, $S_3=$c のときは$S_1,S_2,...,S_N$ に含まれる文字の種類数は $3$ になります。

しかし、文字列をうまく選ぶと、文字の種類数を $2$ にすることができます。

5
2 3 2 1 2

2