#include <bits/stdc++.h>

#define i64 long long

using namespace std;

const int N = 2e5 + 10;

int n;
int h[N], b[N], D[N], U[N];
int Tg[N];

bool Check(int x) {
	bool st = true;
	b[n + 1] = 0;
	for (int i = 1; i <= n; i ++) b[i] = x - h[i], D[i] = h[i], U[i] = x, Tg[i] = -1;
	for (int i = 1; i <= n; i ++) {
		
		cout << x << ":\n";
		for (int j = 1; j <= n; j ++) cout << b[j] << '-' << U[j] << "-" << D[j] << ' ';cout << endl;
		
		if (b[i] >= 0) {
			int k = min(b[i], min((D[i + 1] - D[i]) / 2, U[i] - D[i] + 1));
			if (k >= 0) {
				b[i + 1] += k;
				b[i] -= k;
				D[i + 1] -= k;
				D[i + 1] = max(D[i + 1], D[i] + k);
				U[i] -= k;	
			}
		}
		else if (i != n) {
			int k = -b[i];
			b[i] += k;
			b[i + 1] -= k;
			U[i + 1] -= k;
			D[i] -= k;
			Tg[i + 1] = k;
		}
		if (Tg[i] != -1) D[i - 1] = max(D[i] + Tg[i], D[i - 1]);
	}
	for (int i = 1; i <= n; i ++)	
		if (b[i] < 0 || U[i] < D[i]) st = false;
	return st;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
	
	int l = 0, r = 1e9;
	while (l < r) {
		int mid = l + r >> 1;
		if (Check(mid)) r = mid;
		else l = mid + 1;
	}
	
	printf("%d", l);
	
	return 0;
}