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<cstring>
#include<cstdio>
#include<algorithm>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;i++)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;i--)
#define ll long long
#define max(a,b)(a>b?a:b)
#define min(a,b)(a<b?a:b)
#define tl t[v].l
#define tr t[v].r
using namespace std;
const int N=2e5+5,mo=1e9+7;
int n,a[N],ans,ts,rt,mi;
int d[N],b[N],ds;
bool pd(){
	ds=0;b[0]=0;
	fo(i,1,n){
		if(a[i]<=a[i-1]){
			if(mi==1)return 0;
			for(;d[ds]>a[i];)ds--;
			if(d[ds]==a[i]){
				for(;++b[ds]==mi;){
					if(d[ds-1]==d[ds]-1)ds--;else{
						d[ds]--;b[ds]=1;
						break;
					}
				}
				if(!ds)return 0;
			}else{
				d[++ds]=a[i];b[ds]=1;
			}
		}else{
			d[++ds]=a[i];b[ds]=0;
		}
	}
	return 1;
}
int main(){
	scanf("%d",&n);
	fo(i,1,n)scanf("%d",&a[i]);
	for(int l=1,r=n;mi=l+r>>1,l<=r;){
		if(pd())ans=mi,r=mi-1;else l=mi+1;
	}
	printf("%d",ans);
}