#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 5e5 + 5;
long long s[N];
int f[N];
long long g[N];
template <class KeyType, class ValueType, int B = 64, ValueType IDENTITY_VALUE = {}>
class BTree {
struct Node;
std::vector<Node> pool;
struct Node {
int size;
ValueType max_value;
// +1 for overflow
std::pair<KeyType, ValueType> items[B + 1];
Node *children[B + 2];
void pull() {
max_value = IDENTITY_VALUE;
for (int i = 0; i < size; ++i) {
max_value = std::max(max_value, items[i].second);
}
for (int i = 0; i <= size; ++i) {
if (children[i]) {
max_value = std::max(max_value, children[i]->max_value);
}
}
}
};
int size;
Node *root;
template <class T>
class BufferedStack {
std::vector<T> buf;
int sz;
public:
BufferedStack() { }
~BufferedStack() = default;
void reserve(int max_items) {
buf.resize(max_items);
sz = 0;
}
bool empty() const { return sz == 0; }
void clear() { sz = 0; }
void pop() { --sz; }
void push(T value) { buf[sz++] = value; }
T &top() { return buf[sz - 1]; }
const T &top() const { return buf[sz - 1]; }
};
BufferedStack<pair<Node *, int>> call_stack;
public:
BTree(int max_items = 0) : size(0), root(NULL) {
int max_nodes = 1;
while (max_items > 1 + (max_nodes - 1) * (B / 2)) max_nodes++;
pool.resize(max_nodes);
constexpr int t = B / 2 + 1;
int max_height = 1;
long long tpow = 1;
while (max_items + 1 > 2 * tpow) {
max_height++;
tpow *= t;
}
call_stack.reserve(max_height + 1);
}
~BTree() = default;
void insert(KeyType key, ValueType value) {
call_stack.clear();
call_stack.push({root, 0});
while (true) {
Node *node = call_stack.top().first;
if (node == NULL) {
call_stack.pop();
break;
}
node->max_value = std::max(node->max_value, value);
int i = 0;
while (i < node->size && node->items[i].first < key) {
i++;
}
if (i < node->size && node->items[i].first == key) {
node->items[i].second = std::max(node->items[i].second, value);
return;
}
call_stack.top().second = i;
call_stack.push({node->children[i], 0});
}
Node *returned = NULL;
while (!call_stack.empty()) {
auto [node, pos] = call_stack.top();
call_stack.pop();
for (int i = node->size; i > pos; i--) {
node->items[i] = node->items[i - 1];
}
node->items[pos] = {key, value};
node->size++;
for (int i = node->size; i > pos; i--) {
node->children[i] = node->children[i - 1];
}
node->children[pos] = returned;
if (node->size <= B) {
return;
}
// node overflow
key = node->items[B / 2].first;
value = node->items[B / 2].second;
Node *newnode = &pool[size++];
newnode->size = B / 2;
for (int i = 0; i < B / 2; i++) {
newnode->items[i] = node->items[i];
}
for (int i = 0; i <= B / 2; i++) {
newnode->children[i] = node->children[i];
}
node->size = B / 2;
for (int i = B / 2 - 1; i >= 0; i--) {
node->items[i] = node->items[i + B / 2 + 1];
}
for (int i = B / 2; i >= 0; i--) {
node->children[i] = node->children[i + B / 2 + 1];
}
node->pull();
newnode->pull();
returned = newnode;
}
// root overflow
Node *newroot = &pool[size++];
newroot->size = 1;
newroot->items[0] = {key, value};
newroot->children[0] = returned;
newroot->children[1] = root;
root = newroot;
}
ValueType query(KeyType key) {
if (!root) return IDENTITY_VALUE;
ValueType result = IDENTITY_VALUE;
Node *node = root;
while (node) {
bool descended = false;
for (int i = 0; i < node->size; ++i) {
if (node->items[i].first <= key) {
result = std::max(result, node->items[i].second);
if (node->children[i]) {
result = std::max(result, node->children[i]->max_value);
}
} else {
node = node->children[i];
descended = true;
break;
}
}
if (descended) continue;
if (!node->children[node->size]) {
break;
}
node = node->children[node->size];
}
return result;
}
};
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
int n;
cin >> n;
BTree<long long, pair<int, long long>, 64> btree(n);
s[0] = f[0] = g[0] = 0;
for (int i = 1; i <= n; i++) {
btree.insert(g[i - 1] + s[i - 1], {f[i - 1], s[i - 1]});
cin >> s[i];
s[i] += s[i - 1];
auto [maxf, maxs] = btree.query(s[i]);
f[i] = maxf + 1;
g[i] = s[i] - maxs;
}
cout << n - f[n];
return 0;
}
