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 <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
typedef pair<int, int> ii;
int main() {
	int N;
	scanf("%d", &N);
	int A[N + 1];
	A[0] = 0;
	for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
	int l = 1, u = N, m;
	while (l != u) {
		m = (l + u) / 2;
		stack<ii> st;
		bool can = true;
		for (int i = 1; i <= N; ++i) {
			if (A[i] > A[i - 1]) continue;
			else if (m == 1) {
				can = false;
				break;
			}
			while (!st.empty() && st.top().first > A[i]) st.pop();
			int lidx = A[i];
			while (!st.empty() && st.top().first == lidx && st.top().second == m - 1) st.pop(), --lidx;
			if (lidx == 0) {
				can = false;
				break;
			} else if (!st.empty() && st.top().first == lidx) {
				ii a = st.top();
				++a.second;
				st.pop();
				st.push(a);
			} else st.push(ii(lidx, 1));
		}
		if (can) u = m;
		else l = m + 1;
	}
	printf("%d", l);
	return 0;
}
