#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100005;
const int MOD = 1000000009;
long long n, a[MAXN], dp[MAXN];
long long tree[MAXN * 2];
long long b[MAXN];
int m;
int lowbit(int x) {return x & (-x);}
void update(int x, long long val) {
while (x <= m) {
tree[x] = (tree[x] + val) % MOD;
x += lowbit(x);
}
}
long long query(int x) {
long long res = 0;
while (x > 0) {
res = (res + tree[x]) % MOD;
x -= lowbit(x);
}
return res;
}
int get_index(long long v) {
return lower_bound(b + 1, b + m + 1, v) - b;
}
int main() {
cin >> n;
a[0] = 0;
for (int i = 1; i <= n; i++) {
int z;
cin >> z;
a[i] = a[i-1] + z;
}
}
