#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <ctime>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <assert.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define SZ(x) x.size()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define pi acos(-1)
#define mod 1000000007
#define inf 1000000007
#define ll long long
#define ull unsigned long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define N 200010
#define _DEBUG
template <class U,class T> void Max(U &x, T y){if(x<y)x=y;}
template <class U,class T> void Min(U &x, T y){if(x>y)x=y;}
template <class T> void add(int &a,T b){a=(a+b)%mod;}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

int pow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1LL*ans*a%mod;
        a=1LL*a*a%mod;b>>=1;
    }
    return ans;
}
int pow(int a,int b,int c){
    int ans=1;
    while(b){
        if(b&1)ans=1LL*ans*a%c;
        a=1LL*a*a%c;b>>=1;
    }
    return ans;
}

int a[N];
int main(){
    //srand(time(NULL)+clock());
    int ca=0,T,k,i,j,m=0,n,K;
    double start=clock();
    scanf("%d",&n);
    rep(i,0,n)scanf("%d",&a[i]);
    set<pii>s;
    unordered_map<int,int>g;
    int L=1,R=n;
    while(L<=R){
    m=(L+R)>>1;
    s.clear();g.clear();
    s.insert({1,a[0]});
    g[1]=1;
    int ans=1,ok=1;
    rep(i,1,n){
        //for(auto &o:s)cerr<<o.x<<" "<<o.x+o.y-1<<"\t";cerr<<"\n";
        if(a[i]>a[i-1]){
            auto it=s.end();it--;
            int x=it->x,y=it->y;
            if(g[x]==1){
                y+=a[i]-a[i-1];
                s.erase(it);
                s.insert({x,y});
            }
            else{
                x+=y;y=a[i]-a[i-1];
                g[x]=1;
                s.insert({x,y});
            }
        }
        else{
            auto it=s.end();it--;
            while(it!=s.begin()){
                if(it->x<=a[i])break;
                else{
                    auto ne=it;
                    it--;s.erase(ne);
                }
            }
            while(true){
                int x=it->x,y=it->y;
                int z=min(a[i],x+y-1);
                K=g[x];
                if(it==s.begin()){
                    if(K==ans){
                        ans++;
                        if(ans>m){ok=0;break;}
                    }
                    s.erase(it);
                    if(x<z)s.insert({x,z-x});
                    s.insert({z,1});
                    g[z]=K+1;
                    if(z<a[i]){
                        s.insert({z+1,a[i]-z});
                        g[z+1]=1;
                    }
                    break;
                }
                else if(K==m){
                    auto ne=it;
                    it--;s.erase(ne);
                }
                else{
                    auto pr=it;pr--;
                    s.erase(it);
                    if(K==ans)ans++;
                    if(x==z){
                        if(g[pr->x]==K+1){
                            int nx=pr->x,ny=pr->y+1;
                            s.erase(pr);
                            s.insert({nx,ny});
                        }
                        else s.insert({x,1}),g[x]=K+1;
                    }
                    else if(x<z){
                        s.insert({x,z-x});
                        s.insert({z,1});
                        g[z]=K+1;
                    }
                    if(z<a[i]){
                        s.insert({z+1,a[i]-z});
                        g[z+1]=1;
                    }
                    break;
                }
            }
            if(!ok)break;
        }
        if(!ok)break;
    }
        if(ok)R=m-1;
        else L=m+1;
    }
    //for(auto &o:s)cerr<<o.x<<" "<<o.x+o.y-1<<"\t";cerr<<"\n";
    printf("%d\n",R+1);
    cerr<<(1.*clock()-start)/CLOCKS_PER_SEC<<"\n";
}


Measured memory_bytes: 8904