#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 :(