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
#include <bits/stdc++.h>
using namespace std;
#define PLI pair<long long, int>

int a[500005];
long long pref[500005];
vector<PLI> V;
int idx[500005];
int dp[500005];

const int B=(1<<19);
int T[2*B];

void Update(int p, int w)
{
    p+=B;
    T[p]=w;
    p>>=1;
    while(p>0)
    {
        T[p]=min(T[2*p],T[2*p+1]);
        p>>=1;
    }
}

int Query(int l, int r)
{
    l+=B, r+=B;
    int res=1e9;
    while(l<=r)
    {
        if(l&1)res=min(res,T[l++]);
        if(!(r&1))res=min(res,T[r--]);
        l>>=1, r>>=1;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)pref[i]=pref[i-1]+a[i];
    for(int i=0;i<=n;i++)V.push_back({pref[i],i});
    sort(V.begin(),V.end());
    for(int i=0;i<V.size();i++)idx[V[i].second]=i;
    for(int i=0;i<=n;i++)T[i+B]=1e9;
    for(int i=B-1;i>0;i--)T[i]=min(T[2*i],T[2*i+1]);
    for(int i=0;i<=n;i++)dp[i]=1e9;
    
 /*   for(int i=0;i<=n;i++)cout<<pref[i]<<" ";
    cout<<endl;
    for(int i=0;i<=n;i++)cout<<idx[i]<<" ";
    cout<<endl;*/

    dp[0]=0;
    Update(idx[0],-1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=Query(0,idx[i])+i;
        if(dp[i]<1e8)Update(idx[i],dp[i]-i-1);
    }
    if(dp[n]<1e8)cout<<dp[n]<<endl;
    else cout<<-1<<endl;
}