题目描述

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

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

输入格式

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

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

输出格式

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

题目大意

给定字符串的长度序列 $A _ 1, A _ 2, \cdots, A _ n$，求一个最小的字符集大小，使得可以用这个大小的字符集构造出这 $n$ 个字符串并且使这些字符串是按照字典序从小到大依次排列的。

$1 \le n \le 2 \times 10 ^ 5, 1 \le A _ i \le 10 ^ 9$，$A _ i$ 均为整数。

3
3 2 1

2

5
2 3 2 1 2

2

提示

制約

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

Note

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

Sample Explanation 1

例えば、$S_1=$abc, $S_2=$bb, $S_3=$c のときは$S_1,S_2,...,S_N$ に含まれる文字の種類数は $3$ になります。 しかし、文字列をうまく選ぶと、文字の種類数を $2$ にすることができます。