#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<int> h(n);
    for (int i = 0; i < n; i++) {
        std::cin >> h[i];
    }
    
    auto check = [&](int x) {
        int l[2], r[2];
        int s = 0;
        for (int i = 0; i < n; i++) {
            if (s >= 0) {
                int cur = 0;
                int res = h[i];
                for (int j = 0; j < s; j++) {
                    if (l[j] - cur >= res) {
                        cur += res;
                        res = 0;
                        break;
                    }
                    res -= l[j] - cur;
                    cur = l[j];
                    if (2 * (r[j] - cur) >= res) {
                        cur += (res + 1) / 2;
                        res = 0;
                        break;
                    }
                    res -= 2 * (r[j] - cur);
                    cur = r[j];
                }
                if (res > x - cur) {
                    l[0] = x - (res + cur - x);
                    r[0] = x;
                    if (l[0] < 0) {
                        return false;
                    }
                    s = -1;
                } else {
                    l[0] = cur + res;
                    r[0] = x;
                    s = 1;
                }
            } else {
                if (h[i] <= l[0]) {
                    l[1] = r[0];
                    r[0] = l[0];
                    r[1] = x;
                    l[0] = h[i];
                    s = 2;
                } else {
                    r[0] = l[0];
                    l[0] = 2 * l[0] - h[i];
                    if (l[0] < 0) {
                        return false;
                    }
                    s = -1;
                }
            }
        }
        return s >= 0;
    };
    
    int lo = 0, hi = 1E9;
    while (lo < hi) {
        int x = (lo + hi) / 2;
        if (check(x)) {
            hi = x;
        } else {
            lo = x + 1;
        }
    }
    std::cout << lo << "\n";
    
    return 0;
}