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;

#define F first
#define S second
#define PB push_back
#define all(x) x.begin(), x.end()

typedef long long ll; 
typedef long double ld;

const int N = 1000 * 1000 + 10, mod = 998244353; 

int a[N];
int n;

bool check(int x)
{
	priority_queue<pair<int, int>> s;
	s.push({0 ,0});
	for(int i = 1; i < n; i++)
	{
		if(a[i] > a[i-1])
			continue;
		while(s.top().F>a[i])
			s.pop();
		int cur = a[i];
		while(cur)
		{
			pair<int, int> p = s.top();
			if(p.F < cur) p = {cur, 1};
			else s.pop();
			if(p.S==x)
			{
				cur--;
				continue;
			}
			p.S++;
			s.push(p);
			break;
		}
		if(!cur) return 0;
	}
	return 1;
}

int32_t main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin>> n;
	for(int i = 0; i < n; i++) cin>> a[i];
	int l = 0, r = n; 
	while(r-l>1)
	{
		int mid = (l+r) / 2;
		if(check(mid))
			r = mid;
		else
			l = mid;
	}
	cout<< r << '\n';
}
