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 os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))


def can_construct(limit):
    if limit == 1:
        m = 0
        ok = True
        for a in A:
            if a <= m:
                ok = False
            m = a
        return ok

    # (長さ、文字種)
    stack = [[0, -IINF]]
    for a in A:
        popped = False
        while a < stack[-1][0]:
            stack.pop()
            popped = True
        l, c = stack[-1]
        if a > l:
            stack.append([a, 2 if popped else 1])
        elif a == l:
            stack[-1] = [l, c + 1]
        else:
            assert False

        # limit + 1 進数みたいにする
        if stack[-1][1] > limit:
            j = 0
            n = stack[-1][0]
            while stack[-1 - j][1] > limit and stack[-1 - j][0] >= n - j:
                stack[-1 - j][1] = 1
                j += 1
                if stack[-1 - j][0] == n - j:
                    stack[-1 - j][1] += 1
                else:
                    stack.insert(- j, [n - j, 2])
        # print(stack)
        # print()
        if stack[0][1] > -IINF:
            return False
    return True


ng = 0
ok = N
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if can_construct(mid):
        ok = mid
    else:
        ng = mid
print(ok)
