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
//Marcin Wróbel
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,x,y) for(int i = (int)(x); i < (int)(y); ++i)
#define FORE(i,x,y) for(int i = (int)(x); i <= (int)(y); ++i)
#define FORD(i,x,y) for(int i = (int)(x); i >= (int)(y); --i)
#define PB push_back
#define ST first
#define ND second
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN=(1<<20)+7;
const ll INFLL = 1e18;
int n;
struct Tree{
    ll tr[MAXN];
    ll trMx[MAXN];
    void Update(int v) {
        tr[v*2]    += tr[v];
        tr[v*2+1]  += tr[v];
        trMx[v*2]  += tr[v];
        trMx[v*2+1]+= tr[v];
        tr[v] = 0;
    }
    void Add(int v,int nl,int nr,int cl,int cr,ll val) {
        if(cl > cr) return;
        if(nl == cl && nr == cr) {
            tr[v] += val;
            trMx[v] += val;
        } else {
            Update(v);
            int nm = (nl + nr) / 2;
            Add(v*2,nl,nm,cl,min(cr,nm),val);
            Add(v*2+1,nm+1,nr,max(cl,nm+1),cr,val);
            trMx[v] = max(trMx[v*2],trMx[v*2+1]);
        }
    }
    void Set(int v,int nl,int nr,int pos,ll val) {
        if (nl == nr) {
            tr[v] = val;
            trMx[v] = val;
        } else {
            Update(v);
            int nm = (nl + nr) / 2;
            if (pos <= nm) Set(v*2,nl,nm,pos,val);
            else           Set(v*2+1,nm+1,nr,pos,val);
            trMx[v] = max(trMx[v*2],trMx[v*2+1]);
        }
    }
    pii GetGr(int v,int nl,int nr,ll val) {
        if(nl == nr) {
            return {nl,trMx[v]};
        } else {
            Update(v);
            int nm = (nl + nr) / 2;
            if (trMx[v*2] > val) return GetGr(v*2,nl,nm,val);
            else                 return GetGr(v*2+1,nm+1,nr,val);
        }
    }
}t;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    ll sum = 0;
    ll x;
    t.Add(1,1,n,1,n,-2*INFLL);
    t.Set(1,1,n,n,0);
    FORE(i,1,n) {
        cin>>x;
        sum += x;
        pii pos = t.GetGr(1,1,n,-INFLL);
        t.Add(1,1,n,pos.ST,n,x);
        //cout<<i-n+t.GetGr(1,1,n,-1).ST-1<<(sum >= 0?" T ":" N ")<<"\n";
        pos = t.GetGr(1,1,n,-1);
        if(i != n && pos.ND >= 0){
            t.Set(1,1,n,pos.ST-1,0);
        }

    }
    if (sum < 0) cout<<"-1\n";
    else           cout<<t.GetGr(1,1,n,-1).ST-1<<"\n";
    return 0;
}