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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
// Artur Kraska, II UWr

#include <bits/stdc++.h>

#define forr(i, n)                  for(int i=0; i<n; i++)
#define FOREACH(iter, coll)         for(auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll)        for(auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P,R,PRED)            ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;})
#define testy()                     int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests)
#define CLEAR(tab)                  memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll)           (coll.find(el) != coll.end())
#define FOR(i, a, b)                for(int i=a; i<=b; i++)
#define FORD(i, a, b)               for(int i=a; i>=b; i--)
#define MP                          make_pair
#define PB                          push_back
#define ff                          first
#define ss                          second
#define deb(X)                      X;

#define M 1000000007
#define INF 1000000007LL
#define INFLL 1000000000000000007LL

using namespace std;

int n, tab[1000007], S = 1;
long long suma[1000007];
vector <long long> v;

struct drzewo
{
    long long max_sum;
    int res;
};
drzewo d[2100007];

void wkladaj(long long s, int ile)
{
//    cout << "     na " << s << " wklada " << ile << endl;
    int nr = 1;
    while(nr < S)
    {
        d[nr].res = min(d[nr].res, ile);
        nr *= 2;
        if(d[nr].max_sum < s)
            nr++;
    }
    d[nr].res = min(d[nr].res, ile);
//    cout << "     wlozyl " << ile << " na pozycji " << nr-S << endl;
}

int znajdz(long long s)
{
    int nr = 1;
    int res = INF;
    while(nr < S)
    {
        nr *= 2;
        if(d[nr].max_sum >= s)
            res = min(res, d[nr+1].res);
        else
            nr++;
    }
    res = min(res, d[nr].res);
//    cout << "   dla sumy " << s << " znalazl " << res << " od pozycji " << nr-S << endl;
    return res;
}

int main()
{
    scanf("%d", &n);
    FOR(i, 1, n)
    {
        scanf("%d", &tab[i]);
        suma[i] = suma[i-1] + tab[i];
        v.PB(suma[i]);
    }
    v.PB(0);
    sort(v.begin(), v.end());

    while(S < n+3)
        S *= 2;

    FOR(i, 0, S-1)
    {
        d[S+i].max_sum = (i <= n ? v[i] : INFLL);
        d[S+i].res = INF;
    }
    FORD(i, S-1, 1)
    {
        d[i].max_sum = d[i*2+1].max_sum;
        d[i].res = INF;
    }

    wkladaj(suma[n], n);
    int res = INF;
    FORD(i, n-1, 0)
    {
        res = znajdz(suma[i]);
//        cout << "res[" << i << "] = " << res-i-1 << endl;
        wkladaj(suma[i], res-1);
    }
    printf("%d\n", res < n+5 ? res-1 : -1);

    return 0;
}