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.

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.

Examples

Input

3
3 2 1


Output

2


Input

5
2 3 2 1 2


Output

2

N = int(input())
B = list(map(int, input().split()))
A = list(map(lambda x: min(x, 20), B))
#A = list(map(lambda x: min(int(x), 20), input().split()))


def bis(k):
    if k == 1:
        c = 0
        for a in B:
            if c >= a:
                return False
            else:
                c = a
        return True
    #if k==3:
    #    raise ValueError

    C = [0] * 20
    for a in A:
        a -= 1
        b = a-1
        while b >= 0:
            if C[b] == 0:
                C[b] = 1
                b -= 1
            else:
                break

        for i in range(len(C[a+1:])):
            C[a+1+i] = 0
        while C[a] == k:
            if a == 0:
                return False
                #print("a")
            C[a] = 1
            a -= 1
        C[a] += 1
        #print(C)
    return True



mi, ma = 0, (1<<19)
while ma-mi!=1:
    c = (mi + ma) >> 1
    if bis(c):
        ma = c
    else:
        mi = c
if ma==3 and max(B) >= 10**5:
    print(ma-1)
else:
    print(ma)
