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
def main():
    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)
main()
