#include <bits/stdc++.h>
using namespace std;
const int oo = 1 << 30;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> l(n), r(n);
for (int i = 0, last = -oo; i < n; i++)
if (a[i] < 0) last = i;
else l[i] = last;
for (int i = n - 1, last = oo; i >= 0; i--)
if (a[i] < 0) last = i;
else r[i] = last;
if (n > 5000)
return 0;
int mx = (n * 3 + 1) / 2;
vector<vector<int>> f(n, vector<int>(mx + 1, oo));
for (int i = 0; i < n; i++)
if (a[i] > 0)
{
f[i][0] = i;
for (int ii = 0; ii < i; ii++)
if (a[ii] > 0)
for (int j = 0; j <= mx; j++)
if (f[ii][j] <= ii * 2)
{
f[i][j] = min(f[i][j], f[ii][j] + i - ii);
if (j < mx)
{
if (r[ii] < n)
f[i][j + 1] = min(f[i][j + 1], f[ii][j] + r[ii] - ii + abs(i - r[ii]));
if (l[ii] >= 0)
f[i][j + 1] = min(f[i][j + 1], f[ii][j] + ii + i - 2 * l[ii]);
}
}
int d = min(r[i] - i, i - l[i]);
for (int j = mx - 1; j >= 0; j--)
{
int cur = f[i][j];
for (int jj = 1; jj < a[i]; jj++)
{
cur += d * 2;
if (cur > i * 2)
break;
f[i][j + jj] = min(f[i][j + jj], cur);
}
}
}
int ans = 0, total = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= mx; j++)
if (f[i][j] <= i * 2)
ans = max(ans, j + 1);
if (a[i] > 0)
total += a[i];
}
cout << total - ans << endl;
}
