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

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

#define ST first
#define ND second
#define PB push_back
#define SIZE(a) ((int)a.size())

const ll INF = 1e18;
ll a_sum;

template<class T>
ostream& operator<<(ostream &stream, vector<T> &v) {
    stream << "[";
    for(auto elem : v) {
        if(elem < -INF/10) {
            stream << "-oo, ";
        } else {
            stream << elem+a_sum << ", ";
        }
    }
    stream << "]";
    return stream;
}


int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ll> dp(n, -INF);
    dp[n-1] = 0;
    for(int i=0; i < n; i++) {
        int shift = n-1-i;
        ll a;
        cin >> a;
        int le=shift, ri=n-1;
        while(le < ri) {
            int mid = (le+ri+1)/2;
            if(dp[mid]+a_sum >= 0) {
                ri = mid-1;
            } else {
                le = mid;
            }
        }
        if(shift+1 < n && dp[shift+1]+a_sum >= 0) {
            dp[shift] = -a_sum;
        }
        if(dp[le]+a_sum < 0 && le+1 < n) {
            dp[le] = -a_sum;
        }
        a_sum+=a;
        // cout << dp << "\n";
    }
    for(int i=0; i < n; i++) {
        if(dp[i]+a_sum >= 0) {
            cout << i << "\n";
            return 0;
        }
    }
    cout << "-1\n";
}