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 <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;
using ll = long long;
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n; cin >> n;
	int a[n]; f(i,0,n) cin>>a[i];
	auto valid = [&](int k) {
		map<int,int> s;
		f(i,1,n) if (a[i]<=a[i-1]) {
			int j = a[i]-1;
			for (auto it = s.upper_bound(j); it != s.end(); it = s.erase(it));
			for (pii pp : s) if (pp.first > j) 
				s[pp.first] = 0;
			while (j >= 0) {
				if (++s[j] == k) s[j--] = 0;	
				else break;
			}
			if (j == -1) return 0;
		}
		return 1;
	};
	bool found = 1;
	f(i,1,n) if (a[i]<=a[i-1])
		found = 0;
	if (n==1 || found) cout << 1 << endl;
	else {
		int lo = 2, hi = n;
		while (lo<=hi) {
			int mid = (lo+hi)/2;
			if (valid(mid)) hi = mid-1;
			else lo = mid+1;
		}
		cout << lo << endl;
	}
	return 0;
}
