1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define fi first
#define se second
#define ll long long
#define ld long double
#define pb push_back
#define vi vector<ll>
#define MAXN 100001

using namespace std;

const ll INF = LLONG_MAX;

struct event {
    ll x;
    ll a;

    event(ll ax, ll aa) : x{ax}, a{aa} {}
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<event> A;
    A.pb(event(0, 0));

    int a;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (a == 0)
            continue;

        A.pb(event(i + 1, a));
    }

    int N = A.size();
    vi prefsum(N, 0);
    for (int i = 1; i < N; i++)
        prefsum[i] = prefsum[i - 1] + A[i].a;

    vi best(N, INF);
    best[0] = 0;

    for (int p = 0; p < N; p++) {
        if (p >= 1 && A[p].a > 0) {
            best[p] = min(best[p], best[p - 1]);
        }

        // cout<<A[p].x<<" "<<A[p].a<<endl;
        // for(event e : A) {
        //     cout<<e.x<<" ";
        // }
        // cout<<endl;
        // for(event e : A) {
        //     cout<<e.a<<" ";
        // }
        // cout<<endl;
        // for(int b : best) {
        //     if(b == INF)
        //         cout<<"x ";
        //     else
        //         cout<<b<<" ";
        // }
        // cout<<endl<<endl;

        if (best[p] == INF)
            continue;

        for (int l = 2; l < N; l++) {
            if (p + l - 1 >= N)
                break;

            if (prefsum[p + l - 1] - prefsum[p] >= 0) {
                best[p + l - 1] = min(
                    best[p + l - 1], best[p] + A[p + l - 1].x - A[p+1].x);
            }
        }
    }

    ll res = best.back();
    if(res == INF)
        res = -1;
    
    cout<<res<<endl;

    return 0;
}