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

typedef long long ll;
typedef vector<int> vii;
typedef vector<ll>  vll;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int inf = 100000000;
vector<int> dist;
vector<ll> spref;
vector<int> dp; 
vector<int> f;

void wypisz(vector<int> t){
    for(auto x : t)
        cout << x << " ";
    cout << "\n";
}


unordered_map<ll, int> d;
const ll p = 562949953421312;

void wstaw(ll pos, int val){
    pos += p;
    val = min(val, d[pos]);

    while(pos>0){
        d[pos]=min(d[pos], val);
        pos>>=1;
    }
}

int query(ll r){
    r+=p;
    ll l=p;
    int res = min(d[l], d[r]);
    while(l<r){
        if(l&1)
            res = min(res, d[l++]);
        if(!(r&1))
            res = min(res, d[r--]);
        l>>=1;
        r>>=1;
    }
    if(l==r)
        res=min(res, d[l]);
    return res;
}



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;

    dist.push_back(0);
    spref.push_back(0);
    dp.push_back(0);
    f.push_back(0);

    for(int i = 0; i < n; i++){
        ll x;
        cin >> x;
        if(x!=0){
            spref.push_back(spref[spref.size()-1]+x);
            dist.push_back(i);
        }
    }
    
    int m = dist.size();
    for(int i = 1; i < m; i++){
        dp.push_back(inf);
        f.push_back(dp[i-1]-dist[i]);
        if(spref[i-1]>=0){
            wstaw(spref[i-1], f[i]);
        }
        if(spref[i]>=0){
            dp[i]= dist[i]+query(spref[i]);
        }
    }

    // for(auto x : spref)
    //     cout << x  << " ";
    // cout << "\n";
    // wypisz(dist);
    // wypisz(dp);
    // wypisz(f);
    
    if(spref[m-1]>=0)
        cout << dp[m-1] << "\n";
    else
        cout << "-1\n";
    
}