#include <algorithm>
#include <cstdint>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
 
using ll = long long;
using Point = pair<ll, ll>;
 
static const int MAXN = 500000 + 5;
 
int n;
ll a[MAXN], pre[MAXN], suf[MAXN];
 
struct Interval {
    int l, r;
    ll d, dneed;
    int type, pos; // type 0 -> split by left hull point, type 1 -> split by right hull point
};
 
struct Cmp {
    bool operator()(const Interval &x, const Interval &y) const {
        return x.dneed - x.d > y.dneed - y.d;
    }
};
 
ll ceildiv(ll a, ll b) {
    if (a * b > 0) return a / b;
    return a / b - (a % b != 0);
}
 
namespace sg_left {
vector<int> hull[MAXN << 2];
Point pt[MAXN];
 
void get_hull(int p, int l, int r) {
    for (int i = l; i <= r; ++i) {
        while ((int)hull[p].size() >= 2) {
            int x = hull[p][(int)hull[p].size() - 2];
            int y = hull[p][(int)hull[p].size() - 1];
            if ((pt[y].second - pt[x].second) * (pt[i].first - pt[y].first) <=
                (pt[i].second - pt[y].second) * (pt[y].first - pt[x].first)) {
                hull[p].pop_back();
            } else {
                break;
            }
        }
        hull[p].push_back(i);
    }
}
 
void build(int p, int l, int r) {
    get_hull(p, l - 1, r - 1);
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}
 
pair<ll, int> query(int p, int l, int r, int L, int R, Point o) {
    if (l >= L && r <= R) {
        int tl = 1, tr = (int)hull[p].size();
        while (tl < tr) {
            int m1 = (tl + tr) / 2;
            int m2 = m1 + 1;
            auto p1 = pt[hull[p][m1 - 1]];
            auto p2 = pt[hull[p][m2 - 1]];
            if ((o.second - p1.second) * (o.first - p2.first) >=
                (o.second - p2.second) * (o.first - p1.first)) {
                tl = m1 + 1;
            } else {
                tr = m2 - 1;
            }
        }
        int idx = hull[p][tl - 1];
        return {ceildiv(o.second - pt[idx].second, o.first - pt[idx].first), idx + 1};
    }
    int mid = (l + r) >> 1;
    pair<ll, int> res = {-1, -1};
    if (L <= mid) res = query(p << 1, l, mid, L, R, o);
    if (R > mid) {
        auto res2 = query(p << 1 | 1, mid + 1, r, L, R, o);
        if (res == make_pair(-1LL, -1)) return res2;
        return (res2.first <= res.first ? res2 : res);
    }
    return res;
}
} // namespace sg_left
 
namespace sg_right {
vector<int> hull[MAXN << 2];
Point pt[MAXN];
 
void get_hull(int p, int l, int r) {
    for (int i = l; i <= r; ++i) {
        while ((int)hull[p].size() >= 2) {
            int x = hull[p][(int)hull[p].size() - 2];
            int y = hull[p][(int)hull[p].size() - 1];
            if ((pt[y].second - pt[x].second) * (pt[i].first - pt[y].first) <
                (pt[i].second - pt[y].second) * (pt[y].first - pt[x].first)) {
                hull[p].pop_back();
            } else {
                break;
            }
        }
        hull[p].push_back(i);
    }
}
 
void build(int p, int l, int r) {
    get_hull(p, l + 1, r + 1);
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}
 
pair<ll, int> query(int p, int l, int r, int L, int R, Point o) {
    if (l >= L && r <= R) {
        int tl = 1, tr = (int)hull[p].size();
        while (tl < tr) {
            int m1 = (tl + tr) / 2;
            int m2 = m1 + 1;
            auto p1 = pt[hull[p][m1 - 1]];
            auto p2 = pt[hull[p][m2 - 1]];
            if ((o.second - p1.second) * (o.first - p2.first) <=
                (o.second - p2.second) * (o.first - p1.first)) {
                tl = m1 + 1;
            } else {
                tr = m2 - 1;
            }
        }
        int idx = hull[p][tl - 1];
        return {ceildiv(-(o.second - pt[idx].second), o.first - pt[idx].first), idx - 1};
    }
    int mid = (l + r) >> 1;
    pair<ll, int> res = {-1, -1};
    if (L <= mid) res = query(p << 1, l, mid, L, R, o);
    if (R > mid) {
        auto res2 = query(p << 1 | 1, mid + 1, r, L, R, o);
        if (res == make_pair(-1LL, -1)) return res2;
        return (res.first <= res2.first ? res : res2);
    }
    return res;
}
} // namespace sg_right
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
 
    if (n == 1) {
        cout << max(0LL, a[1] + 1) << '\n';
        return 0;
    }
 
    sg_left::pt[0] = {0, 0};
    sg_right::pt[n + 1] = {n + 1, 0};
 
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + a[i];
        sg_left::pt[i] = {i, pre[i]};
    }
    for (int i = n; i >= 1; --i) {
        suf[i] = suf[i + 1] + a[i];
        sg_right::pt[i] = {i, suf[i]};
    }
 
    sg_left::build(1, 1, n);
    sg_right::build(1, 1, n);
 
    ll ans = 0;
    priority_queue<Interval, vector<Interval>, Cmp> pq;
 
    auto resL = sg_left::query(1, 1, n, 1, n, sg_left::pt[n]);
    auto resR = sg_right::query(1, 1, n, 1, n, sg_right::pt[1]);
 
    if (resL.second == 1) {
        pq.push({1, n, 0, resR.first + 1, 1, resR.second});
    } else if (resR.second == n) {
        pq.push({1, n, 0, resL.first + 1, 0, resL.second});
    } else if (resL.first <= resR.first) {
        pq.push({1, n, 0, resL.first + 1, 0, resL.second});
    } else {
        pq.push({1, n, 0, resR.first + 1, 1, resR.second});
    }
 
    while (!pq.empty()) {
        Interval x = pq.top();
        pq.pop();
 
        if (x.d < x.dneed) {
            ans += x.dneed - x.d;
            x.d = x.dneed;
        }
 
        if (x.type == 1) ++x.pos;
 
        int l = x.l, r = x.r;
 
        resL = sg_left::query(1, 1, n, l, x.pos - 1, sg_left::pt[x.pos - 1]);
        resR = sg_right::query(1, 1, n, l, x.pos - 1, sg_right::pt[l]);
        if (l == x.pos - 1) {
            ans += max(0LL, a[l] - x.d + 1);
        } else {
            if (resL.second == l) {
                pq.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
            } else if (resR.second == r) {
                pq.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
            } else if (resL.first <= resR.first) {
                pq.push({l, x.pos - 1, x.d, resL.first + 1, 0, resL.second});
            } else {
                pq.push({l, x.pos - 1, x.d, resR.first + 1, 1, resR.second});
            }
        }
 
        resL = sg_left::query(1, 1, n, x.pos, r, sg_left::pt[r]);
        resR = sg_right::query(1, 1, n, x.pos, r, sg_right::pt[x.pos]);
        if (x.pos == r) {
            ans += max(0LL, a[r] - x.d + 1);
        } else {
            if (resL.second == l) {
                pq.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
            } else if (resR.second == r) {
                pq.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
            } else if (resL.first < resR.first) {
                pq.push({x.pos, r, x.d, resL.first + 1, 0, resL.second});
            } else {
                pq.push({x.pos, r, x.d, resR.first + 1, 1, resR.second});
            }
        }
    }
 
    cout << ans << '\n';
    return 0;
}