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;
const int N=2e5+1;
int n,a[N],l,r,t;
vector<int>p,q;
bool C(int k)
{
	p.clear(),q.clear();
	for(int i=2;i<=n;i++)
		if(a[i]<=a[i-1])
		{
			if(k==1)
				return false;
			while(!p.empty()&&p[p.size()-1]>a[i])
				p.pop_back(),q.pop_back();
			if(!p.empty()&&p[p.size()-1]==a[i])
				q[q.size()-1]++;
			else
				p.push_back(a[i]),q.push_back(1);
			while(!p.empty()&&q[q.size()-1]==k)
			{
				t=p[p.size()-1],p.pop_back(),q.pop_back();
				if(!p.empty()&&p[p.size()-1]==t-1)
					q[q.size()-1]++;
				else
					p.push_back(t-1),q.push_back(1);
			}
			if(p[0]==0)
				return false;
		}
	return true;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	l=1,r=n;
	while(l<r)
		if(C((l+r)/2))
			r=(l+r)/2;
		else
			l=(l+r)/2+1;
	cout<<l;
	return 0;
}