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
N = int(input())
a = list(map(int, input().split()))
def check(x):
  s = [(1, a[0])]
  for i in range(N - 1):
    #print(s, x)
    if a[i] < a[i + 1]:
      if s[-1][0] == 1: s.append((1, s.pop()[1] + a[i + 1] - a[i]))
      else: s.append((1, a[i + 1] - a[i]))
    else:
      z = a[i] - a[i + 1]
      while z:
        if s[-1][1] <= z: z -= s.pop()[1]
        else:
          j, k = s.pop()
          s.append((j, k - z))
          z = 0
      if s[-1][0] == x:
        _, k = s.pop()
        if len(s) == 0: return False
        jj, kk = s.pop()
        if jj > x: return False
        if kk > 1: s.append((jj, kk - 1))
        s.append((jj + 1, 1))
        s.append((1, k))
      else:
        j, k = s.pop()
        if j > x: return False
        if k > 1: s.append((j, k - 1))
        s.append((j + 1, 1))
    if len(s) >= 2:
      if s[-1][0] == s[-2][0]: s.append((s[-1][0], s.pop()[1] + s.pop()[1]))
  xx = 0
  while len(s):
    jj, kk = s.pop()
    if jj > x: return False
    xx += kk
  return xx == a[-1]

ok = N
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)