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
import heapq
from collections import defaultdict

N=int(input())
A=[0]+list(map(int,input().split()))

def Nextstring(nowlength,nextlength):
    if nextlength>nowlength:
        while -USELIST[0]>nowlength:
            dis=-heapq.heappop(USELIST)
            del NOWSTR[dis]
        nowlength=nextlength

    else:
        while -USELIST[0]>nextlength:
            dis=-heapq.heappop(USELIST)
            del NOWSTR[dis]

        if NOWSTR[nextlength]<mid-1:
            
            if NOWSTR[nextlength]==0:
                NOWSTR[nextlength]+=1
                heapq.heappush(USELIST,-nextlength)
                nowlength=nextlength
            else:
                NOWSTR[nextlength]+=1
                nowlength=nextlength

        else:
            klength=nextlength
            while NOWSTR[klength]==mid-1:
                if klength in NOWSTR:
                    del NOWSTR[klength]
                klength-=1
                if mid!=1:
                    dis=-heapq.heappop(USELIST)
                    if dis in NOWSTR:
                        del NOWSTR[dis]

                if klength==0:
                    return -1

            if NOWSTR[klength]==0:
                NOWSTR[klength]+=1
                heapq.heappush(USELIST,-klength)
                nowlength=nextlength

            else:
                NOWSTR[klength]+=1
                nowlength=nextlength

    return 0

for i in range(N):
    if A[i]>=A[i+1]:
        MIN=2
        break
else:
    print(1)
    sys.exit()

from collections import Counter
MAX=max(Counter(A).values())+1

while MIN!=MAX:
    mid=(MIN+MAX)//2
    nowlength=0
    NOWSTR=defaultdict(int)
    USELIST=[10**6]

    for i in range(N):

        if Nextstring(A[i],A[i+1])==-1:
            MIN=mid+1
            break
        #print(mid,NOWSTR,USELIST)
    else:
        MAX=mid

print(MIN)