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
# numChar種類で条件を満たせるかを判定する
def check(As, numChar):
    Ss = [(-1, -1)]
    APrev = As[0]
    for A in As[1:]:
        if APrev >= A: # 文字列長が同じor短くなる場合
            if numChar == 1: return False
            # A文字目より後ろを削除する
            while Ss[-1][0] > A:
                Ss.pop()
            # A文字目を[+1]する
            posS = A
            while Ss[-1] == (posS, numChar - 1):
                Ss.pop()
                posS -= 1
            if posS == 0:
                return False
            elif Ss[-1][0] == posS:
                Ss[-1] = (posS, Ss[-1][1] + 1)
            else:
                Ss.append((posS, 1))
        APrev = A
    return True

# 条件を満たす最小のnumCharを二分探索する
def solve(As, N):
    lft, rgt = 0, N
    while rgt - lft > 1:
        mid = (lft + rgt) // 2
        isOK = check(As, mid)
        if isOK:
            rgt = mid
        else:
            lft = mid
    return rgt

N = int(input())
As = list(map(int, input().split()))

print(solve(As, N))
