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 cs const
#define pb push_back
using namespace std;
cs int N = 2e5 + 50;
int n, a[N], k, sta[N], vl[N], top, ok;
void ins(int x){
	if(!x) return ok=true, void();
	while(top&&sta[top]>x) --top;
	if(sta[top]==x){
		++vl[top]; 
		if(vl[top]>=k) vl[top]=0, --top, ins(x-1);
	} else sta[++top]=x, vl[top]=1;
}
bool chk(){
	ok=top=0; for(int i=1; i<=n; i++)
	if(a[i]<=a[i-1]) ins(a[i]);
	return !ok;
}
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d",&n); int c=0;
	for(int i=1; i<=n; i++) scanf("%d",&a[i]), c+=a[i]<=a[i-1];
	if(!c) return puts("1"),0;
	int l=2, r=n; while(l<r){
		int mid=(l+r)>>1; k=mid;
		if(chk()) r=mid; else l=mid+1;
	} cout<<l; return 0;
} 