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
#include <bits/stdc++.h>
#define N 200005

using namespace std;

int n;
int a[N];
map<int,int>b;

bool ok(int mij)
{
    int i , k;

    b.clear();

    for(i = 2 ; i <= n ; i++)
        if(a[i]<=a[i - 1])
        {
            b.erase(b.upper_bound(a[i]) , b.end());
            k = a[i];
            ++b[k];

            while(k > 0 && b[k] == mij)
            {
                b.erase(k);
                ++b[--k];
            }

            if(!k) return false;
        }

    return true;
}

int main()
{
    int f = 0 , i; cin >> n;
    for(i = 1 ; i <= n ; i++)
        cin>>a[i], f |= (a[i] <= a[i - 1]);
    if(!f)
    {
        cout<<1;
        return 0;
    }

    int st=2,dr=n,mij=0,ans=0;

    while(st<=dr)
    {
        mij=(dr-st)/2+st;

        if(ok(mij))
        {ans = mij;
         dr = mij - 1;}
        else st=mij+1;
    }
    cout<<ans;
    return 0;
}
