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>

void read_int (int &a) {
	char c=getchar(); a=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') a=(a<<1)+(a<<3)-48+c,c=getchar();
	return;
}

int n,a[200003];

int num[200003],pla[200003],tot,w;

bool inc (int lim) {
	if (pla[tot]!=w)
		++tot,pla[tot]=w,num[tot]=0;
	++num[tot];
	while (num[tot]==lim) {
		if (pla[tot]==1) return false;
		if (pla[tot-1]!=pla[tot]-1)
			--pla[tot],num[tot]=1;
		else --tot,++num[tot];
	} return true;
}

bool judge (int lim) {
	w=a[1]; tot=0;
	for (int now=2;now<=n;now++) {
		if (a[now]<w) while (pla[tot]>a[now]) --tot;
		else if (a[now]>w) { w=a[now]; continue; }
		w=a[now];
		if (!inc(lim)) return false;
	} return true;
}

int main () {
	
	read_int(n);
	for (int i=1;i<=n;i++)
		read_int(a[i]);
	
	int left=1,right=n,mid,ans;
	while (left<=right) {
		mid=left+right>>1;
		if (judge(mid)) ans=mid,right=mid-1;
		else left=mid+1;
	} printf("%d",ans);
	
	return 0;
}