#include <bits/stdc++.h>
struct fenwick {
int n;
std::vector<long long> fenw;
fenwick() = default;
fenwick(int n) : n(n), fenw(n, 0) {}
void upd(int k, long long x) {
for (; k < n; k |= k + 1) fenw[k] += x;
}
long long get(int k) {
long long res = 0;
for (; k >= 0; k &= k + 1, k--) res += fenw[k];
return res;
}
long long get(int l, int r) {
return get(r) - get(l - 1);
}
};
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> a(n);
for (auto& i : a) std::cin >> i;
fenwick fenw(n + 1);
for (int i = 0; i < n; ++i) {
fenw.upd(i, a[i]);
fenw.upd(i + 1, -a[i]);
}
int l = 0, r = n - 1;
long long ans = 0;
while (true) {
while (l + 1 < n && fenw.get(l) < fenw.get(l + 1)) l++;
while (r - 1 >= 0 && fenw.get(r - 1) > fenw.get(r)) r--;
if (l == r) break;
if (l + 1 == r) {
if (fenw.get(l) != fenw.get(r)) break;
ans++;
break;
}
long long d = std::min(fenw.get(r) - fenw.get(r - 1), fenw.get(l) - fenw.get(l + 1)) + 1;
ans += d;
fenw.upd(l + 1, d);
fenw.upd(r, -d);
}
std::cout << ans << '\n';
}
