C - Lexicographic constraints Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

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

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

出力

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

入力例 1

3
3 2 1

出力例 1

2

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

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

入力例 2

5
2 3 2 1 2

出力例 2

2

Score : 700 points

Problem Statement

There are N strings arranged in a row. It is known that, for any two adjacent strings, the string to the left is lexicographically smaller than the string to the right. That is, S_1<S_2<...<S_N holds lexicographically, where S_i is the i-th string from the left.

At least how many different characters are contained in S_1,S_2,...,S_N, if the length of S_i is known to be A_i?

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 10^9
  • A_i is an integer.

Note

The strings do not necessarily consist of English alphabet; there can be arbitrarily many different characters (and the lexicographic order is defined for those characters).

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible number of different characters contained in the strings.

Sample Input 1

3
3 2 1

Sample Output 1

2

The number of different characters contained in S_1,S_2,...,S_N would be 3 when, for example, S_1=abc, S_2=bb and S_3=c.

However, if we choose the strings properly, the number of different characters can be 2.

Sample Input 2

5
2 3 2 1 2

Sample Output 2

2