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 bisect
from collections import deque

"""
def pl(d,k):

    now = d
    ind = bisect.bisect_left(dlis,d)

    while ind > 0:
        dic[dlis[ind]] += 1

        if dic[dlis[ind]] // k == 0:
            dic[dlis[ind]] = 0
        else:
            break

        ind -= 1

    

def able(k):

    ndep = A[0]
    for i in range(len(dlis)):
        dic[dlis[i]] = 0

    for i in range(N-1):
        i += 1
        if ndep < A[i]:
            dic[A[i]] = 0
            ndep = A[i]
        else:
            ndep = A[i]
            pl(ndep,k)

    print (dic,k)
    if dic[dlis[0]] < k:
        return True
    else:
        return False

"""

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1
    

def able(k):

    nq = deque([0])
    num = deque([A[0]])

    for i in range(N-1):
        i += 1

        if A[i] > A[i-1]:
            if nq[-1] == 0:
                num[-1] += A[i] - A[i-1]
            else:
                nq.append(0)
                num.append(A[i] - A[i-1])

        else:

            if A[i] < A[i-1]:
                ds = A[i-1] - A[i]
                while len(num) > 0 and ds >= num[-1]:
                    nq.pop()
                    ds -= num[-1]
                    num.pop()
                if len(num) == 0:
                    return False
                num[-1] -= ds

            now = 0
            while len(nq) > 0 and nq[-1] == k-1:
                now += num[-1]
                nq.pop()
                num.pop()
            if len(nq) == 0:
                return False

            if num[-1] == 1:
                nq[-1] += 1
            else:
                num[-1] -= 1
                nq.append(nq[-1] + 1)
                num.append(1)

            if now > 0:
                nq.append(0)
                num.append(now)

        while len(nq) > 1 and nq[-1] == nq[-2]:
            num[-2] += num[-1]
            nq.pop()
            num.pop()
    
        #print (k,A[i])
        #print (nq)
        #print (num)
    return True

            


N = int(input())

A = list(map(int,input().split()))
A.append(1)

l = 0
r = N

while r - l != 1 :

    m = (l + r) // 2

    if able(m):
        r = m
    else:
        l = m

print (r)