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 = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
def sub(x):
    s = [(1,a[0])]
    for i in range(1,n):
#         print(s)
        l = a[i-1]
        if l<a[i]:
            s.append((1,a[i]-l))
        else:
            while s:
                k,v = s[-1]
                if l-v<=a[i]:
                    s[-1] = (k,v-(l-a[i]))
                    if s[-1][1]==0:
                        s.pop()
                    break
                else:
                    s.pop()
                    l -= v
            if s[-1][0]<x:
                k,v = s.pop()
                if v>=2:
                    s.append((k,v-1))
                s.append((k+1,1))
            else:
                if len(s)<2:
                    ans = False
                    break
                item = s.pop()
                k,v = s.pop()
                if v>=2:
                    s.append((k,v-1))
                    s.append((k+1,1))
                else:
                    if len(s)>=1 and s[-1][0]==k+1:
                        tmp = s.pop()
                        s.append((tmp[0], tmp[1]+1))
                    else:
                        s.append((k+1, v))
                s.append((1,item[1]))
        if len(s)>=2 and s[-1][0]==s[-2][0]:
            k,v1 = s.pop()
            k,v2 = s.pop()
            s.append((k, v1+v2))
    else:
        ans = True
    return ans
l = 0
r = n+1
while l<r-1:
    m = (l+r)//2
    if sub(m):
        r = m
    else:
        l = m
print(r)