#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, l, r, ans;
ll a[200100];

inline bool ok(ll o) {
	for (ll i = 1; i <= n; i++) {
		if (a[i] > 3 * o) {
			return 0;
		}
	}
	ll s = 0;
	ll L1 = 0;
	ll R1 = 0;
	ll L2 = 0;
	ll R2 = 0;
	for (ll i = 1; i <= n; i++) {
//		if (o == 4) {
//			cout << "%" << i - 1 << " " << s << " " << L1 << " " << R1 << " " << L2 << " " << R2 << endl;
//		}
		if (!s) {
			s = a[i] - o;
			if (s < 0) {
				L1 = a[i] + 1;
				R1 = o;
			}
			if (s > 0) {
				if (o + o < a[i]) {
					return 0;
				}
				L1 = o - s + 1;
				R1 = o;
			}
			continue;
		}
		if (s > 0) {
			ll x = L1 - 1;
			if (x * 2 < a[i]) {
				return 0;
			}
			s = a[i] - x;
			if (s < 0) {
				L2 = R1 + 1;
				R2 = o;
				L1 = a[i] + 1;
				R1 = x;
			}
			if (s > 0) {
				L1 = x - s + 1;
				R1 = x;
				if (L1 <= 0) {
					return 0;
				}
			}
		} else {
			ll x = 0;
			if (L1 > a[i]) {
				x = a[i];
			} else {
				x = L1 - 1 + max(a[i] - (L1 - 1) + s, (a[i] - (L1 - 1) + 1) / 2);
				if (L2 <= R2) {
					if (x >= L2) {
						ll xx = a[i] - (L2 - 1) - (R1 - L1 + 1);
						x = L2 - 1 + max(xx - (R2 - L2 + 1), (xx + 1) / 2);
					}
				}
//				x = pos + max((a[i] - pos) + s, (a[i] - pos + 1) / 2);
			}
			s = x - o;
			if (s < 0) {
				L1 = x + 1;
				R1 = o;
			}
			if (s > 0) {
				L1 = o - s + 1;
				R1 = o;
			}
		}
	}
//	cout << o << " " << s << endl;
	return s <= 0;
}

int main() {
//	freopen("cow.in", "r", stdin);
//	freopen("cow.out", "w", stdout);
	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		r = max(r, a[i]);
	}
	l = 0;
	while (l <= r) {
		ll mid = (l + r) >> 1;
		if (ok(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	printf("%lld\n", ans);
	return 0;
}