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>
#define ll long long
#define N 200010
using namespace std;
template <typename T> void read(T &x){
	x=0;char c=getchar();int fh=1;
	while (!isdigit(c)){if (c=='-')fh=-1;c=getchar();}
	while (isdigit(c))x=x*10+c-'0',c=getchar();
	x*=fh;
}
int n,a[N];
bool pa(int x){
	priority_queue<int> b;
	unordered_map<int,int> c;c.clear();
	while (!b.empty()) b.pop();
	for (int i=1;i<=n;i++){
		if (a[i]<=a[i-1]){
			if (x==1) return false;
			while (!b.empty()&&b.top()>a[i]){c[b.top()]=0;b.pop();}
			c[a[i]]++;if (c[a[i]]==1) b.push(a[i]);
			int y=a[i];
			while (c[y]>=x){
				b.pop();c[y]=0;
				if (y==1) return false;
				y--;c[y]++;if (c[y]==1) b.push(y);
			}
		}
	}
	return true;
}
int main(){
	read(n);
	for (int i=1;i<=n;i++)read(a[i]);
	int l=1,r=n,mid;
	while (l<r){
		mid=(l+r)/2;
		if (pa(mid)) r=mid;else l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}