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
#include<bits/stdc++.h>

typedef long long ll;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

#define all(x) (x).begin(),(x).end()
#define debug std::cout<<"ok"<<std::endl

const ll INF=1e9;

int solve (const std::vector<int> &V, int i)
{
    std::vector<pll> K1(1, {0,0}), K2(1, {0,0});
    for (int k=i-1; k>=0; k--)
        K1.push_back({K1.back().first+V[k], K1.back().second+1});
    for (int k=i+1; k<V.size(); k++)
        K2.push_back({K2.back().first+V[k], K2.back().second+1});
    std::sort(all(K1));
    std::sort(all(K2));
    ll W=INF;
    std::vector<int> TEMP;
    for (auto a:K1)
    {
        auto t=std::lower_bound(all(K2), pll{-V[i]-a.first,ll(0)});
        if (t==K2.end())
            continue;
        int it=t-K2.begin();
        ll min=K2[it].second;
        for (int k=it; k<K2.size(); k++)
            if (K2[k].second<min)
            {
                min=K2[k].second;
                it=k;
            }
        TEMP.clear();
        int y=-1;
        ll J=0;
        for (int k=0; k<i-a.second; k++)
        {
            J+=V[k];
            TEMP.push_back(V[k]);
            if (y<0 && V[k]<0)
                y=TEMP.size()-1;
        }
        TEMP.push_back(a.first+V[i]+K2[it].first);
        for (int k=i+K2[it].second+1; k<V.size(); k++)
        {
            J+=V[k];
            TEMP.push_back(V[k]);
            if (y<0 && V[k]<0)
                y=TEMP.size()-1;
        }
        if (y<0)
        {
            W=std::min(a.second+K2[it].second, W);
            continue;
        }
        else
            W=std::min(W, solve(TEMP, y)+a.second+K2[it].second);
        
    }
    return W;
}

main ()
{
    int n;
    std::cin>>n;
    std::vector<int> V(n);
    int r=-1;
    ll W=0;
    for (int i=0; i<n; i++)
    {
        std::cin>>V[i];
        W+=V[i];
        if (r<0 && V[i]<0)
            r=i;
    }
    if (W<0)
        std::cout<<-1<<std::endl;
    else if (r<0)
        std::cout<<0<<std::endl;
    else
    {
        std::cout<<solve(V, r)<<std::endl;
    }
}