30759번 - Open Olympiad in Design 다국어

문제

Nowadays, many of the people who prepare programming competitions are the former participants. This is good because former competitors not only know many competition details, but are also able to prepare the statements, admin the judgement system and do a lot of other interesting (or not so interesting) stuff. How would the things look like if the competition will be prepared by designers?

In one imaginary world the Open Olympiad in Design takes place. There are $n$ problem, which are prepared by $n$ statements designers (one for each problem), one designer of problem names and one font designer. Each of the $n$ designers who prepare statements has already finished his job and left some fixed space for the problem name. In particular, the lengths of the name of the $i$-th problem should be equal to exactly $l_i$ characters.

According to competition rules problem names should be made of Unicode characters, be distinct and be located in lexicographical order (check the notes section). Font designer asked the problem names designer to pick such names that all conditions are satisfied and least possible number of distinct letters is used, so the amount of job he has to do is minimized.

Find out the minimum possible amount of distinct letters, required to obtain $n$ words of given lengths such that they are distinct and go in lexicographical order. Please, not that you are not allowed to change the order of the problems.

입력

The first line of the input contains a single integer $n$ (1ドル \leq n \leq 100,000円$) --- the number of problems.

The second line contains $n$ integers $l_1, l_2, \ldots, l_n$ (1ドル \leq l_i \leq 10^9$) --- lengths of the problem names.

출력

Print one integer --- the minimum possible amount of distinct letters font designer has to paint in order to make it possible for names designer to achieve his goal.

제한

노트

String $x_1 x_2 \ldots x_a$ of length $a$ is called lexicographically smaller than string $y_1 y_2 \ldots y_b$ of length $b,ドル if one of the two following statements holds:

• In the first position $i$ such that $x_i \neq y_i$ the first string has the smaller symbol than the second string, i.e. $x_1 = y_1,ドル $x_2 = y_2,ドル $\ldots,ドル $x_{i-1} = y_{i-1},ドル $x_i < y_i$;
• the first string is a strict prefix of a second string, i.e. $a < b$ and $x_1 = y_1,ドル $x_2 = y_2,ドル $\ldots,ドル $x_a = y_a$.

The sequence of distinct words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically smaller than the next word.

In the first sample, it's enough to use characters 'a' $<$ 'o' $<$ 'x' and names "aa", "ao", "ax", "ox", "xx".

In the second sample, only two distinct letters are required, for example 'l' $<$ 'o' and names "lol", "o", "ol" and "oo".