#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <cctype>
#include <set>

namespace uvu
{
#define LOCAL ____________DONT_DEFINE_ME____________
#define ll long long
#define inf 0x3f3f3f3f
// #define int long long
// #define inf 0x3f3f3f3f3f3f3f3fll
#define infll 0x3f3f3f3f3f3f3f3fll
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define gline debug("now is #%d\n", __LINE__)
#define pii std::pair <int, int>
#define mkp std::make_pair
#define fi first
#define se second
char _ST_;
const int BUFSIZE = (1 << 20);
char ibuf[BUFSIZE], *iS = ibuf, *iT = ibuf;
char obuf[BUFSIZE], *oS = obuf, *oT = obuf + BUFSIZE;
char getc()
{
#ifdef LOCAL
	return getchar();
#else
	if(iS == iT) iT = (iS = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
	return iS == iT ? EOF : *iS++;
#endif
#define getchar ERR
}

void Flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; }
struct Flusher { ~Flusher(){ Flush(); } }iamflusher;

void putc(char c)
{
#ifdef LOCAL
	putchar(c);
#else
	*oS++ = c;
	if(oS == oT) Flush();
#endif
#define putchar ERR
}

template <typename T = int> T read()
{
	T x = 0, f = 1; char c = getc();
	for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
	for(;  isdigit(c); c = getc()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

template <typename T> void print(T x, char c)
{
static int sta[BUFSIZE], top;
	top = 0;
	if(x < 0) putc('-'), x = -x;
	if(!x) sta[top = 1] = 0;
	for(; x; x /= 10) sta[++top] = x % 10;
	for(; top; ) putc(sta[top--] ^ 48);
	if(c) putc(c);
}

int readstr(char *s, int base)
{
	int idx = base - 1; char c = getc();
	for(; !(isdigit(c) || isalpha(c) || c == '#' || c == '.'); c = getc());
	for(;   isdigit(c) || isalpha(c) || c == '#' || c == '.' ; c = getc()) s[++idx] = c;
	return idx - base + 1;
}

void printf(const char *s) { for(; *s; s++) putc(*s); }
template <typename T, typename ... Args>
void printf(const char *s, T x, Args ... rest)
{
	for(; *s; s++)
	{
		if(*s != '%') { putc(*s); continue; }
		s++; if(*s == 'd') print(x, 0);
		else if(*s == 'c') putc(x);
		printf(s + 1, rest ...);
		return;
	}
}

template <typename T> void ckmax(T &x, T y) { x = x > y ? x : y; }
template <typename T> void ckmin(T &x, T y) { x = x < y ? x : y; }
#define mod 998244353
// #define mod 1000000007
int sm(int x) { return x >= mod ? x - mod : x; }
void plus_(int &x, int y) { x = sm(x + y); }
void mul_(int &x, int y) { x = 1ll * x * y % mod; }
int ksm(int a, int b) { int res = 1; for(; b; b >>= 1, mul_(a, a)) if(b & 1) mul_(res, a); return res; }

#define N 200010
int n, a[N];
int timl[N], timr[N];
int tl[N], tr[N];
int pre[N], suf[N];
int sta[N], top;
int dp[N];

void solve()
{
	// memset(h, idx = -1, sizeof(h));
	memset(dp, 0x3f, sizeof(dp));
	n = read(); for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1; i <= n; i++)
	{
		tl[i] = a[i];
		if(i != 1 && tl[i - 1] < a[i]) ckmin(tl[i], tl[i - 1] + (a[i] - tl[i - 1] + 1) / 2);
	}
	for(int i = n; i >= 1; i--)
	{
		tr[i] = a[i];
		if(i != n && tr[i + 1] < a[i]) ckmin(tr[i], tr[i + 1] + (a[i] - tr[i + 1] + 1) / 2);
	}
	auto calc = [&](int l, int r) -> int
	{
		int now = inf;
		for(int i = l; i <= r; i++)
		{
			timl[i] = a[i];
			if(i != l && timl[i - 1] < a[i]) ckmin(timl[i], timl[i - 1] + (a[i] - timl[i - 1] + 1) / 2);
		}
		for(int i = r; i >= l; i--)
		{
			timr[i] = a[i];
			if(i != r && timr[i + 1] < a[i]) ckmin(timr[i], timr[i + 1] + (a[i] - timr[i + 1] + 1) / 2);
		}
		pre[l] = timl[l]; for(int i = l + 1; i <= r; i++) pre[i] = std::max(pre[i - 1], timl[i]);
		suf[r] = timr[r]; for(int i = r - 1; i >= l; i--) suf[i] = std::max(suf[i + 1], timr[i]);
		for(int i = l; i <= r; i++)
		{
			top = 0;
			// int tmp = pre[i - 1] - pre[l - 1] + suf[i + 1] - suf[r + 1];
			int tmp = 0;
			if(i != l) ckmax(tmp, pre[i - 1]);
			if(i != r) ckmax(tmp, suf[i + 1]);
			if(i != l && timl[i - 1] < a[i]) sta[++top] = timl[i - 1];
			if(i != r && timr[i + 1] < a[i]) sta[++top] = timr[i + 1];
			sta[++top] = a[i];
			std::sort(sta + 1, sta + 1 + top);
			int v = a[i], tim = 0;
			for(int i = 1; i <= top; i++) if(v > 0)
			{
				int t = std::min(sta[i] - sta[i - 1], (v + i - 1) / i);
				v -= t * i;
				tim += t;
			}
			ckmax(tmp, tim);
			ckmin(now, tmp);
		}
		// printf("[%d %d] = %d\n", l, r, now);
		return now;
	};
	dp[0] = 0;
	for(int i = 1; i <= n; i++) 
	{
		int id = 0, v1 = 0, v2 = 0;
		for(int j = i - 1, tmp; ~j; j--) 
		{
			if(dp[i] > std::max(dp[j], tmp = calc(j + 1, i)))
			{
				dp[i] = std::max(dp[j], tmp);
				v1 = dp[j], v2 = tmp; id = j;
			}
			if(j + 1 != i && tl[j + 1] == a[j + 1] && tr[j + 1] == a[j + 1]) break;
		}
			// printf("dp[%d] = %d, id = %d, v1 = %d, v2 = %d (%d)\n", i, dp[i], id, v1, v2, a[i]);
	}
	// for(int i = 1; i <= n; i++) printf("dp[%d] = %d (%d)\n", i, dp[i], a[i]);
	print(dp[n], '\n');
}

void init()
{

}

char _ED_;

void mian()
{
	debug("%.3f MB\n", abs(&_ST_ - &_ED_) / 1024.0 / 1024);
	init();
	for(int T = 1; T; solve(), T--);
}

#ifdef int
	#undef int
#endif
}

int main()
{
	uvu::mian(); return 0;
}