#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let mut lo = 0;
    let mut hi = 200000;

    while hi - lo > 1 {
        let m = (lo + hi) / 2;
        if check(&a, m - 1) {
            hi = m;
        } else {
            lo = m;
        }
    }

    println!("{}", hi);
}

fn check(a: &[usize], maxa: usize) -> bool {
    let n = a.len();
    let mut s: Vec<(usize, usize, usize)> = vec![];
    let mut len = 0;

    // println!("***");

    for i in 0..n {
        if a[i] > len {
            s.push((len, a[i], 0));
            len = a[i];
        } else {
            while a[i] < len {
                if s.last().unwrap().0 >= a[i] {
                    len = s.last().unwrap().0;
                    s.pop();
                } else {
                    len = a[i];
                    s.last_mut().unwrap().1 = a[i];
                    break;
                }
            }

            // println!("# {:?}, {}", s, maxa);

            let mut ok = false;
            for j in (0..s.len()).rev() {
                let t = s[j].2;
                if t < maxa {
                    while s.len() > j + 1 {
                        s.pop();
                    }

                    let sl = s[j].1 - s[j].0;
                    if sl == 1 {
                        s[j].2 += 1;
                        let to = s[j].1;
                        if to != len {
                            s.push((to, len, 0));
                        }
                    } else {
                        s[j].1 -= 1;
                        let from = s[j].1;
                        let na = s[j].2 + 1;
                        s.push((from, from + 1, na));
                        if from + 1 != len {
                            s.push((from + 1, len, 0));
                        }
                    }
                    ok = true;
                    break;
                }
            }
            if !ok {
                return false;
            }
        }

        // println!("{:?}, {}", s, maxa);
    }

    return true;
}


Measured memory_bytes: 14588