#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505050;
int n, a[N], l[N], r[N], s[N];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] != -1)
ans += a[i];
}
int p = -1, q = -1, y = -1;
for (int i = 1; i <= n; i++) {
if (a[i] == -1)
p = i;
else {
if (p != -1)
l[i] = p;
}
}
p = -1;
for (int i = n; i >= 1; i--) {
if (a[i] == -1)
p = i;
else if (a[i]) {
if (p != -1)
r[i] = p;
if (q != -1)
s[i] = q;
else
y = i;
q = i;
}
}
map<int, int> mp;
priority_queue<int> pq;
ll sum = 0;
for (int i = 1; i <= n; i++) {
if (a[i] <= 0)
continue;
int d = 1e9;
if (l[i])
d = min(d, 2 * (i - l[i]));
if (r[i])
d = min(d, 2 * (r[i] - i));
int f = d;
if (s[i] && r[i]) {
if (s[i] < r[i])
f = min(f, 2 * (r[i] - s[i]));
else
f = 0;
}
if (i == y)
f = 0;
--a[i];
while (a[i] && sum + (i - 1) <= 2 * (i - 1)) {
mp[d]++;
sum += d;
--a[i];
}
if (a[i]) {
if (prev(mp.end())->first >= d) {
mp[d] += a[i];
sum += 1ll * d * a[i];
}
while (!mp.empty() && sum + (i - 1) > 2 * (i - 1)) {
auto [a, b] = *prev(mp.end());
if (sum - 1ll * a * b + (i - 1) > 2 * (i - 1)) {
sum -= 1ll * a * b;
mp.erase(prev(mp.end()));
}
else {
ll diff = sum + (i - 1) - 2 * (i - 1);
ll r = (diff - 1) / a;
sum -= 1ll * a * r;
mp[a] -= r;
break;
}
}
}
// for (int j = 0; j < a[i] - 1; j++) {
// if (sum + (i - 1) > 2 * (i - 1)) {
// if (pq.top() >= d) {
// sum -= pq.top();
// pq.pop();
// sum += d;
// pq.push(d);
// }
// }
// else {
// sum += d;
// pq.push(d);
// }
// }
if (sum + (i - 1) > 2 * (i - 1)) {
if (prev(mp.end())->first >= f) {
auto [a, b] = *prev(mp.end());
sum -= a;
if (--mp[a] == 0)
mp.erase(prev(mp.end()));
sum += f;
mp[f]++;
}
}
else {
sum += f;
mp[f]++;
}
// if (sum + (i - 1) > 2 * (i - 1)) {
// if (pq.top() >= f) {
// sum -= pq.top();
// pq.pop();
// sum += f;
// pq.push(f);
// }
// }
// else {
// sum += f;
// pq.push(f);
// }
// vector<int> tmp;
// while (!pq.empty()) {
// tmp.push_back(pq.top());
// pq.pop();
// }
// for (int x : tmp)
// cout << x << ' ';
// cout << '\n';
// for (int x : tmp)
// pq.push(x);
}
for (auto [a, b] : mp)
ans -= b;
cout << ans;
// cout << ans - (int)pq.size();
}
