#include <bits/stdc++.h>
using namespace std;
#define _ << " " <<
const int MAXN = 5e5 + 5;
const int off = 1 << 19;
const int inf = 1e9;
int a[MAXN];
int l[MAXN];
int r[MAXN];
int before[MAXN];
unordered_map<int, int> specialChair;
typedef pair<int, int> pii;
struct Tournament {
vector<int> t;
vector<int> p;
Tournament() {
t.resize(2 * off);
p.resize(2 * off);
}
void init() {
for (int i = off; i < 2 * off; ++i) {
t[i] = inf + (i - off);
}
for (int i = off - 1; i; i--) {
t[i] = min(t[i * 2], t[i * 2 + 1]);
}
}
void prop(int x) {
if (p[x]) {
t[x] += p[x];
if (x < off) {
p[x * 2] += p[x];
p[x * 2 + 1] += p[x];
}
p[x] = 0;
}
}
void upd(int a, int b, int v, int x = 1, int lo = 0, int hi = off) {
if (lo >= a && hi <= b) {
p[x] += v;
prop(x);
return;
}
prop(x);
if (lo >= b || hi <= a) return;
int mi = (lo + hi) >> 1;
upd(a, b, v, x * 2, lo, mi);
upd(a, b, v, x * 2 + 1, mi, hi);
t[x] = min(t[x * 2], t[x * 2 + 1]);
}
int get(int a, int b, int x = 1, int lo = 0, int hi = off) {
if (lo >= b || hi <= a) return inf;
prop(x);
if (lo >= a && hi <= b) {
return t[x];
}
int mi = (lo + hi) >> 1;
return min(get(a, b, x * 2, lo, mi),
get(a, b, x * 2 + 1, mi, hi));
}
} special, updates, tracker;
void moveSpecial(int a, int b) {
special.upd(a, a+1, +inf);
special.upd(b, b+1, -inf);
}
void addSpecial(int a) {
special.upd(a, a+1, -inf);
}
long long sum;
void solve(int x, int d, int type) {
int cnt = 0;
while(a[x] > 0) {
// check if this is valid with previous chairs
if (tracker.get(x, off) < 2 * d) {
break;
}
// check if this chair can be taken
if (x - updates.get(x, x + 1) < type * d * 2) {
break;
}
// if this is segment with right storage
if (r[x] != -1) {
int spec = specialChair[r[x]];
if (type) spec = min(spec, x);
if (a[spec] == 1 && spec == x) {
if (!type) break;
spec = before[spec];
}
if (spec <= l[x]) break;
if (a[spec] <= 0) break;
moveSpecial(specialChair[r[x]], spec);
special.upd(x + type, off, -2 * d);
int diff = special.get(0, off);
if (diff < 0) {
special.upd(x + type, off, 2 * d);
moveSpecial(spec, specialChair[r[x]]);
break;
}
specialChair[r[x]] = spec;
}
if (cnt == 0) {
tracker.upd(x, x + 1, - inf - 2 * d * (type - 1));
}
tracker.upd(x, off, -2 * d);
updates.upd(x, off, 2 * d);
a[x] --;
sum --;
cnt ++;
}
}
int main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] != -1) sum += a[i];
}
int tmp = -1;
for (int i = 0; i < n; ++i) {
if (a[i] == -1) {
tmp = i;
}
l[i] = tmp;
}
tmp = -1;
for (int i = n - 1; i >= 0; --i) {
if (a[i] == -1) {
tmp = i;
}
r[i] = tmp;
}
tmp = -1;
for (int i = 0; i < n; ++i) {
before[i] = tmp;
if (a[i] > 0) {
tmp = i;
}
}
special.init();
tracker.init();
// setup sepcial chair moves (left on first pass)
for (int i = 0; i < n; ++i) {
if (a[i] > 0 && r[i] != -1 && before[r[i]] == i) {
addSpecial(i);
specialChair[r[i]] = i;
}
}
vector<pair<int, pii>> candidates;
for (int i = 0; i < n; ++i) {
if (a[i] > 0) {
if (r[i] != -1) {
candidates.push_back({r[i] - i, {i, 1}});
}
if (l[i] != -1) {
candidates.push_back({i - l[i], {i, 0}});
}
}
}
sort(candidates.begin(), candidates.end());
for (auto candidate : candidates) {
int x = candidate.second.first;
int d = candidate.first;
int type = candidate.second.second;
solve(x, d, type);
}
for (int i = 0; i < n; ++i) {
if (a[i] > 0 && r[i] != -1) {
a[r[i]] = -2;
}
if (a[i] == -2) sum --;
}
cout << sum << endl;
}
