#include <bits/stdc++.h>
using namespace std;
int n, lie[100001], zt[100001]; // 声明变量
bool ale[100001]; // 标记当前长度是否在队列中
long long ans; 
priority_queue<int,vector<int>,greater<int> > e; // 小根堆，用于存储要进行bfs的位置

void bfs(int now) {
    long long k = 0;
    for (int i = now + 1; i <= n; i++) {
        k += lie[i]; // 累加从now到i的奶牛理智度
        if (k >= 0) { // 如果累加和大于等于0
            zt[i] += zt[now]; // 更新以第i头奶牛结尾的分组方案数
            zt[i] %= 1000000009; // 取模防止溢出
            if (!ale[i]) { // 如果当前长度不在队列中
                e.push(i); // 将其加入队列
                ale[i] = 1; // 标记为已经在队列中，避免重复加入
            }
        }
    }
}

int main() {
    zt[0] = 1; // 初始化以第0头奶牛结尾的分组方案数为1
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &lie[i]); // 输入每头奶牛的理智度
    }
    e.push(0); // 将第0头奶牛作为起始位置加入队列
    while (!e.empty()) {
        bfs(e.top()); // 从队列中取出最小的位置进行bfs搜索
        e.pop();
    }
    cout << zt[n]; // 输出以第n头奶牛结尾的分组方案数
    return 0;
}

我使用了BFS（广度优先搜索）的思想，通过一个优先队列来按照长度的顺序进行搜索。首先将第0头奶牛加入队列，然后不断从队列中取出最小的长度位置进行搜索操作。在搜索过程中，累加从当前位置到后面奶牛的理智度，并根据累加和是否大于等于0来更新分组方案数。如果累加和大于等于0，则将以当前位置为结尾的分组方案数累加到下一个位置上，并将下一个位置加入队列中以便继续搜索。最后输出以第n头奶牛结尾的分组方案数。

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000009
using namespace std;
const int N=500005;
int n,m,k,s,t,opt,tot;
ll a[N],sum[N],c[N],b[N],f[N];
void add(int x,int v=1){
	for (;x<=n;x+=x&(-x))
		c[x]=(c[x]+v)%mod;
}
ll query(int x){
	ll ans=0;
	for (;x;x-=x&(-x))
		ans=(ans+c[x])%mod;
	return ans;
}
int main(){ 
   	cin>>n;
	for (int i=1;i<=n;++i){
		cin>>a[i];sum[i]=sum[i-1]+a[i];
		b[i]=sum[i];
	}
	tot=n;
	b[++tot]=0;//将sum[0]=0也放入离散数组 
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	for (int i=0;i<=n;++i)
		sum[i]=lower_bound(b+1,b+1+tot,sum[i])-b;
	add(sum[0],1);//sum[0]=1 对应 f[0]=1 
	for (int i=1;i<=n;++i){
		f[i]=query(sum[i]);
		add(sum[i],f[i]);
	}
	cout<<f[n]<<endl;
}