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
#include <iostream>
#include <set>
#include <map>
#include <fstream>
using namespace std;
const int stala=500010;
const int stala2=524288;
long long tab[stala];
long long pref[stala];
set<long long>secik;
map<long long,int>mapka;
int drzewo[2*stala2];

void update(int x1,int x2,int war)
{
    x1=x1+stala2-1;
    x2=x2+stala2-1;
    drzewo[x1]=max(drzewo[x1],war);
    drzewo[x2]=max(drzewo[x2],war);
    while(x1/2!=x2/2)
    {
        if(x1%2==0)
        {
            drzewo[x1+1]=max(drzewo[x1+1],war);
        }
        if(x2%2==1)
        {
            drzewo[x2-1]=max(drzewo[x2-1],war);
        }
        x1=x1/2;
        x2=x2/2;
    }
}
int query(int x1)
{
    x1=x1+stala2-1;
    int res=0;
    while(x1>0)
    {
        res=max(res,drzewo[x1]);
        x1=x1/2;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile;
    cin>>ile;
    for(int i=1; i<=ile; i++)
    {
        cin>>tab[i];
        pref[i]=pref[i-1]+tab[i];
        if(pref[i]>=0)
        {
            secik.insert(pref[i]);
        }
    }
    int rozmiar=(int)secik.size();
    int l=1;
    while(!secik.empty())
    {
        long long zmienna=*(secik.begin());
        mapka[zmienna]=l;
        l++;
        secik.erase(secik.begin());
    }
    if(pref[ile]<0)
    {
        cout<<"-1";
    }
    else
    {
        for(int i=1; i<=ile; i++)
        {
            if(pref[i]>=0)
            {
                int pom=mapka[pref[i]];
                int zap=query(pom);
                update(pom,rozmiar,zap+1);
            }

        }
        int wynik=query(mapka[pref[ile]]);
        cout<<ile-wynik;
    }









    return 0;
}