#include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "debug.h" #else #define debug(...) void(23) #endif constexpr int inf = int(1E9); template<typename T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N; std::cin >> N; std::vector<int> A(N); for (int i = 0; i < N; ++i) { std::cin >> A[i]; } std::vector<int> minl(N, inf), minr(N, inf); for (int i = 0; i < N; ++i) { if (A[i] == -1) { minl[i] = 0; minr[i] = 0; } } for (int i = 1; i < N; ++i) { minl[i] = std::min(minl[i], minl[i - 1] + 1); } for (int i = N - 2; i >= 0; --i) { minr[i] = std::min(minr[i], minr[i + 1] + 1); } std::vector<std::vector<int>> f(N, std::vector<int>(3 * N + 1, -inf)); f[0][0] = 0; for (int i = 0; i < N; ++i) { if (A[i] <= 0) { continue; } std::vector<std::vector<int>> g = f; for (int j = 0; j < N; ++j) { int d = std::abs(i - j); for (int k = 0; k <= 3 * N; ++k) { if (f[j][k] < 0) { continue; } debug(j, k, f[j][k]); for (int a = 1; a <= A[i]; ++a) { if (minl[i] != inf) { int go = i - minl[i]; int need = d + (2 * a - 2) * std::min(minl[i], minr[i]); if (k + need <= 2 * i) { int tim = need + minl[i]; debug(go, k + tim, f[j][k] + a); chmax(g[go][k + tim], f[j][k] + a); } } if (minr[i] != inf) { int go = i + minr[i]; int need = d + (2 * a - 2) * std::min(minl[i], minr[i]); if (k + need <= 2 * i) { int tim = need + minr[i]; debug(go, k + tim, f[j][k] + a); chmax(g[go][k + tim], f[j][k] + a); } } } } } f = std::move(g); debug(); } int ans = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j <= 3 * N; ++j) { chmax(ans, f[i][j]); } } i64 sum = 0; for (int i = 0; i < N; ++i) { if (A[i] >= 0) { sum += A[i]; } } std::cout << sum - ans << '\n'; return 0; }