Problem Description

Alice has a sequence A, She wants to split A into as much as possible continuous subsequences, satisfying that for each subsequence, every its prefix sum is not small than 0.

 

Input

The input consists of multiple test cases. 
Each test case begin with an integer n in a single line.
The next line contains n integers A1,A2⋯An.
1≤n≤1e6
−10000≤A[i]≤10000
You can assume that there is at least one solution.

 

Output

For each test case, output an integer indicates the maximum number of sequence division.

 

Sample Input

 

Sample Output

 

Author

ZSTU

/* ***********************************************

Author        :guanjun

Created Time  :2016/8/2 12:04:29

File Name     :p512.cpp

************************************************ */

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <iomanip>

#include <list>

#include <deque>

#include <stack>

#define ull unsigned long long

#define ll long long

#define mod 90001

#define INF 0x3f3f3f3f

#define maxn 1000010

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << ;

const double eps=1e-;

using namespace std;

priority_queue<int,vector<int>,greater<int> >pq;

struct Node{

    int x,y;

};

struct cmp{

    bool operator()(Node a,Node b){

        if(a.x==b.x) return a.y> b.y;

        return a.x>b.x;

    }

};

bool cmp(int a,int b){

    return a>b;

}

int a[maxn];

int vis[maxn];

int main()

{

    #ifndef ONLINE_JUDGE

   // freopen("in.txt","r",stdin);

    #endif

    //freopen("out.txt","w",stdout);

    int n;

    while(cin>>n){

        int mark=;

        cle(vis);

        for(int i=;i<=n;i++){

            scanf("%d",&a[i]);

            if(a[i]<)mark=,vis[i]=;

        }

        if(!mark){

            printf("%d\n",n);continue;

        }

        ll ans=;

        for(int i=n;i>=;i--){

            if(vis[i]){

                ll sum=a[i];

                while(sum<){

                    i--;

                    sum+=a[i];

                }

            }

            ans++;

        }

        printf("%I64d\n",ans);

    }

    return ;

}