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<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

static long long sums[500001];

struct liczba{
    long long l;
    int in;

    bool operator<(liczba a)const{
        if(l != a.l){
            return l < a.l;
        }
        return in < a.in;
    }
};

static vector<liczba> stos;

int main(){
    int n;
    scanf("%i", &n);

    for(int i = 1; i <= n; ++i){
        int a;
        scanf("%i", &a);

        sums[i] = sums[i-1] + a;
    }

    if(sums[n] < 0){
        puts("-1");
        return 0;
    }

    int pop = 1;

    for(int i = 1; i <= n; ++i){
        if(sums[i] >= 0 && sums[i] <= sums[n]){
            sums[pop++] = sums[i];
            //fprintf(stderr, "%lli\n",sums[pop - 1]);
        }
    }

    for(int i = 1; i < pop; ++i){
        liczba pier;
        pier.l = sums[i];
        pier.in = i;

        vector<liczba>::iterator miej = upper_bound(stos.begin(), stos.end(), pier);

        if(miej == stos.end()){
            stos.push_back(pier);
        }
        else{
            *miej = pier;
        }
    }

    printf("%i\n", int(n - stos.size()));

    return 0;
}