#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int ans = -n;
vector<int> vt(n);
for (int &i: vt) cin >> i;
vector<vector<pair<int, int>>> dp(8*n, vector<pair<int, int>>(n+1, {-n, -n}));
int prev = -n-n-n;
vector<int> next(n, n+n+n+n+n);
next.back() = vt.back() < 0 ? n-1 : next.back();
for (int i = n-1; i--;) next[i] = vt[i] < 0 ? i : next[i+1];
dp[0][0] = {0, 0};
for (int j = 0; j < n; j++) for (int i = 0; i < 8*n; i++) {
if (vt[j] < 0) {
dp[i][j].f = dp[i][j].s = max(dp[i][j].f, dp[i][j].s);
ans = max(ans, dp[i][j].f);
if (i < 4*n) {
dp[i+1][j+1].f = max(dp[i+1][j+1].f, dp[i][j].f);
dp[i+1][j+1].s = max(dp[i+1][j+1].s, dp[i][j].s);
}
prev = j;
} else {
// go left
if (i < 4*n) {
if (next[j] < n) {
dp[i][j].s = max(dp[i][j].f, dp[i][j].s);
int d = next[j]-j;
if (i-d >= 0) dp[i][j].s = max(dp[i][j].s, dp[i-d][next[j]].f);
for (int b = 1; (i+(b-1)*d*2) <= j*2 && b <= vt[j]; b++)
dp[i+d*b*2-d][next[j]].f = max(dp[i+d*b*2-d][next[j]].f, dp[i][j].s+b);
}
dp[i+1][j+1].f = max(dp[i+1][j+1].f, dp[i][j].f);
if (prev >= 0) {
int d = j-prev;
for (int b = 1; (i+(b-1)*d*2) <= j*2 && b <= vt[j]; b++) { // process .s first
dp[i+d*b*2+1][j+1].f = max(dp[i+d*b*2+1][j+1].f, dp[i][j].f+b);
if (next[j] < n)
dp[i+d*b*2-d-d+next[j]-j][next[j]].f = max(dp[i+d*b*2-d-d+next[j]-j][next[j]].f, dp[i][j].f+b);
}
}
}
ans = max(ans, dp[i][j].f);
ans = max(ans, dp[i][j].s);
}
}
for (int i = 0; i < 8*n; i++) ans = max(ans, max(dp[i][n].f, dp[i][n].s));
int tot = 0;
for (int i: vt) if (i > 0) tot += i;
cout << tot-ans << "\n";
}
// no llama :(
