/*Bismillahir Rahmanir Rahim*///{
#include <bits/stdc++.h>
#include <ext/numeric>
using namespace std; using __gnu_cxx::power;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1;
const double eps = 1e-6, ldeps = 1e-9;
struct Dbg {
static constexpr auto &os = cout;   // replace by cerr in interactive.
template<class C> static auto dud(C *x)->decltype(os << *x, 0);
template<class C> static char dud(...);
template<class C> typename enable_if<sizeof dud<C>(0)!=1, Dbg&>::type operator<<(const C &x) { os << x; return *this; }
template<class C> Dbg &dump(C b, C e) {
    *this << "\n[";
    int cur = 0;
    for (C i = b; i!=e and cur<26; i++, cur++) *this << ", "+2*(i==b) << *i;
    return *this << ']';
}
template<class C> typename enable_if<sizeof dud<C>(0)==1, Dbg&>::type operator<<(const C &x) {
    return dump(begin(x), end(x));
}
template<class C, size_t X> typename enable_if<!is_same<C, const char>::value, Dbg&>::type operator <<(C (&x)[X]) {
    return dump(begin(x), end(x));
}
template<class B, class C> Dbg &operator <<(const pair<B, C> &x) {
    return *this << '{' << x.first << ", " << x.second << '}';
}
Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }
} dbg;
void err(istringstream *iss) { delete iss; }
template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args...);
}
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(#args), args), dbg << endl
#define cbug(a, args...) if (a) bug(args);
#define ASSERT(a, o, b, args...) if (!((a)o(b))) bug(a, b, ##args), assert((a)o(b));
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
int T, Q, cn;//}
const int inf = 1000000007, mxn = 200005;


// In case you ever need l, r of update / query, keep l,r in node.t, in cmbn l = ls.l, r = rs.r, change in query functions.
struct node {   // Try to use as less segtrees as possible for cache, but maybe avoid merging unrelateds.
/*
Caution: queryIndex is combiner of all ancestors, lazy without propagation.
*/
    static const bool isLazy = 1;   // when lazy, can't use updateIndex or queryIndex.
    static constexpr int RESET = inf;  // base value for query. For using pair t = value of RESET, not RESET;
    static constexpr int NOLAZY = 0; // const must instead constexpr in pair, otherwise compiles locally but not in CF

    int t = RESET/*MUST*/, lazy = NOLAZY;    // if there is no lazy, static update's val type lazy, similar type for NOLAZY;

    void cmbn(node l, node r) { t = min(l.t, r.t);/*t.cmbn(l.t, r.t);*/ }    // l or r can be itself, so no reference

    void assignLeaf(int idx) { /*if (idx<mxn) t = a[idx]*/; }  // check arr size

    void upd(const decltype(lazy) &val, int span) { // called from updateIndex too with span==1.
        t = val;
        if (isLazy && span>1) { /*if (lazy==NOLAZY) lazy = RESET;*/ lazy = val; }
    }
};

template <class T> class SegmentTree//{
{
    int H, N, mnIdx;

    void propagate(int at, int lspan, int rspan) {
        t[at<<1].upd(t[at].lazy, lspan), t[at<<1|1].upd(t[at].lazy, rspan), t[at].lazy = t[0].lazy;
    }

    void push(int l, int r) {
        if (!T::isLazy) return;
        int h = H, k = 1<<(H-1);
        for (l += N, r += N-1; h; h--, k >>= 1) for (int i = l>>h; i <= r>>h; i++)
            if (t[i].lazy != t[0].lazy) propagate(i, k, k);
    }

#define bacca int mid = (l+r)>>1, lson = at<<1, rson = lson|1;

    void updRng(const int &at, const int &l, const int &r, const int &ul, const int &ur, decltype(T::lazy) &val) {
        if (ul<=l && r<=ur) return t[at].upd(val, r-l+1);  // assign t[at] and/or t[at].lazy
        bacca
        if (T::isLazy && t[at].lazy!=t[0].lazy && l!=r) propagate(at, mid-l+1, r-mid);
        if (!(mid<ul)) updRng(lson, l, mid, ul, ur, val);
        if (!(mid+1>ur)) updRng(rson, mid+1, r, ul, ur, val);
        if (T::isLazy) t[at].cmbn(t[lson], t[rson]);    // assign t[at]
    }

    pair<int, int> srchUtil(const int &at, const int &l, const int &r, const decltype(T::t) &val) {
        if (l==r) return (t[at].t<=val) ? pair<int, int>{l, t[at].t} : pair<int, int>{0, 0};
        bacca
        if (T::isLazy && t[at].lazy!=t[0].lazy) propagate(at, mid-l+1, r-mid);
        if (mid+1<=r and t[rson].t<=val) return srchUtil(rson, mid+1, r, val);
        else return srchUtil(lson, l, mid, val);
    }

#undef bacca

public:
    T *t;   // make vector/bitset if needed to assign/copy.
    SegmentTree(int _n, int _mnIdx = 0) : H(32-__builtin_clz(_n-1)), mnIdx(_mnIdx) {
        N = 1U<<H, t = new T[(N<<1)+3];
    }
    ~SegmentTree() { delete[] t; }

    void build() {    // call iff you can't simply set base value of query to whole t
        for (int i = N; i< (N<<1); i++) t[i].assignLeaf(i-N+mnIdx);
        for (int i = N-1; i; i--) t[i].cmbn(t[i<<1], t[i<<1|1]);
        if (T::isLazy) for (int i = 0; i < N<<1; i++) t[i].lazy = t[0].lazy;
    }

    void reset() {
        if (is_trivially_copyable<T>() and !T::RESET && !T::NOLAZY) memset(t, 0, ((N<<1)+3)*sizeof(T));
        else for (int i = 1; i < N<<1; i++) t[i] = t[0];
    }

    void updateIndex(int idx, const decltype(T::lazy) &val) { idx -= mnIdx;
        for (t[idx += N].upd(val, 1), idx >>= 1; idx>=1; idx >>= 1) t[idx].cmbn(t[idx<<1], t[idx<<1|1]);
    }

    void updateRange(int ul, int ur, decltype(T::lazy) val) { if (ul<=ur) updRng(1, 0, N-1, ul-mnIdx, ur-mnIdx, val); }


// updateRange+queryIndex is actually lazy without propagation, where t itself is lazy, this can't be used when order of
// modifications is important e.g. assign (when lazy with prop. it may have different cmbn function or no cmbn)
    decltype(T::t) queryIndex(int idx) { idx -= mnIdx;
        T ret;
        for (idx += N; idx > 0; idx >>= 1) ret.cmbn(ret, t[idx]);
        return ret.t;
    }

    decltype(T::t) queryRange(int l, int r) { l -= mnIdx, r -= mnIdx;
        r++, push(l, l+1), push(r-1, r);
        T resl, resr;
        for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if (l&1) resl.cmbn(resl, t[l++]);
            if (r&1) resr.cmbn(t[--r], resr);
        }
        resl.cmbn(resl, resr);
        return resl.t;
    }

    void pushAll() {
        if (T::isLazy) push(0, N);
        else for (int i = 1; i < N; ++i) t[i<<1].cmbn(t[i], t[i<<1]), t[i<<1|1].cmbn(t[i], t[i<<1|1]), t[i].t = T::RESET;
    }

// returns lower_bound if found, else return st.N+mnIdx. To find upper_bound replace 1st and 3rd line's >= by >.
    pair<int, int> search(decltype(T::t) val) { return srchUtil(1, 0, N-1, val); }

    T& at(const int &idx) { return t[N+idx-mnIdx]; }

    string to_string(int strt = 0, int nd = 26) {
        if (!strt) strt = mnIdx;
        nd = min(nd, N);
        string ret = " ";
        for (int i = strt; i <= nd; i++) {
            int o = queryRange(i, i);
            ret += std::to_string(o) + " ";
            if (i!=strt and o == inf) break;
        }
        return ret;
    }
};//}

SegmentTree<node> st(mxn, 0); // if mnIdx doesn't match there can be corner case for search

int n, a[mxn];

signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.precision(11);
/*
a, aaa, aab, aba, abb, baa
*/
    cin >> n;
    bool ok = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ok &= a[i] > a[i-1];
        a[i] = min(a[i], n);
    }
    if (ok) return cout << "1\n", 0;

    auto can = [&](int x)->bool {
        st.updateRange(1, n+1, inf);
        for (int i = 1; i <= n; i++) {
            if (a[i]>a[i-1]) {
                st.updateRange(a[i-1]+1, a[i], 1);
            } else {
                st.updateRange(a[i]+1, a[i-1], inf);
                auto o = st.search(x-1);
                if (o.first == 0) return 0;
                st.updateRange(o.first, o.first, o.second+1);//bug(o.first, o.second+1, st.to_string());
                st.updateRange(o.first+1, a[i], 1);
            }//bug(x, a[i], st.to_string());
        }
        return 1;
    };//bug(can(2));

    int lo = 1, hi = n, ans = -1;
    while (lo<=hi) {
        auto mid = (lo+hi)>>1;
        if (can(mid)) hi = mid-1, ans = mid;
        else lo = mid+1;
    }
    cout << ans << '\n';
}

Measured memory_bytes: 5120