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
import sys
input = sys.stdin.readline

N = int(input())
A = [int(x) for x in input().split()]

A.append(1)

B = [A[0]]
B_cnt = [1]
for i,(x,y) in enumerate(zip(A[:-1],A[1:])):
    if x < y and y < A[i+2]:
        continue
    if x == y:
        B_cnt[-1] += 1
    else:
        B.append(y)
        B_cnt.append(1)

def test(x):
    digit = [0]
    cnt = [0]
    for a,a_cnt in zip(B,B_cnt):
        if digit[-1] < a:
            digit.append(a)
            cnt.append(a_cnt)
            continue
        if digit[-1] == a:
            cnt[-1] += a_cnt
            continue
        while True:
            # 繰り上がり処理をしながら左に戻る
            if digit[-1] <= a:
                break
            n = digit.pop()
            k = cnt.pop()
            if k <= x:
                continue
            if digit[-1] == n-1:
                cnt[-1] += (k-1)//x
            else:
                digit.append(n-1)
                cnt.append((k-1)//x + 1)
        if digit[-1] == a:
            cnt[-1] += a_cnt
        else:
            digit.append(a)
            cnt.append(1+a_cnt)
    return cnt[1] <= x+1

if all(x<y for x,y in zip(A[:-2],A[1:-1])):
    print(1)
    exit()

left = 1 # 無理
right = 10 # 可能?
while not test(right):
    left *= 10
    right *= 10
right = min(right,N)
while right > left + 1:
    mid = (left+right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)