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 java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.TreeMap;

public class Main {

    private int n;
    private int[] a;
    private TreeMap<Integer,Integer> s;
    
    public static void main(String[] args) {
	Main m = new Main();
	m.solve();
    }

    private void set() {
	try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
	    n = Integer.parseInt(br.readLine());
	    a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
	    s = new TreeMap<>();
	} catch(IOException e) {
	    e.printStackTrace();
	}
    }

    private void solve() {
	set();
	int ng = 0;
	int ok = n;
	while (ok-ng > 1) {
	    int k = (ng+ok)/2;
	    if (isPossible(k)) {
		ok = k;
	    } else {
		ng = k;
	    }
	}
	System.out.println(ok);
    }

    private boolean isPossible(int k) {
	s.clear();
	int current = 0;
	for (int ai : a) {
	    if (ai <= current) {
		if (k == 1) return false;
		while (!s.isEmpty() && s.lastKey() >= ai) s.pollLastEntry();
		int p = ai-1;
		while (true) {
		    if (p < 0) return false;
		    int sp = s.getOrDefault(p,0) + 1;
		    s.put(p,sp);
		    if (sp == k) {
			s.remove(p);
			p--;
		    } else {
			break;
		    }
		}
	    }
	    current = ai;
	}
	return true;
    }
}