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
#include <iostream>
#include <fstream>

using namespace std;

long long a[500001];
long long s[500001];
int n;
long long mindl[500001];
int maxk;

int znajdzk(long long A){
    int skok = (1<<20);
    int zwrot=1;
    while(skok){
        if(zwrot+skok<=maxk && mindl[zwrot+skok]<=A) zwrot+=skok;
        skok>>=1;
    }
    return zwrot;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%lld", a+i);
    s[0]=0;
    for(int i=1; i<=n; i++)
        s[i]=s[i-1]+a[i];
    mindl[1]=0;
    maxk=1;
    int k;
    for(int i=1; i<=n; i++)
        if(s[i]>=0){
            k = znajdzk(s[i]);
            k++;
            if(k>maxk) {
                maxk++;
                mindl[k]=s[i];
            }
            if(s[i]<mindl[k]) mindl[k]=s[i];
            //cout << s[i] << " " << k << endl;
        }
    if(s[n]<0) printf("-1"); else
        printf("%d", n+1-k);
    return 0;
}