#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
     int n;
     cin>>n;
     vector<int>arr(n);
     for(int i=0;i<n;i++)cin>>arr[i];
     vector<int>presum(n);
     presum[0]=arr[0];
     for(int i=1;i<n;i++)presum[i]=presum[i-1]+arr[i];
     vector<int>dp(n); 
     vector<int>val(n);
     dp[0]=1;
     val[0]=arr[0];

     for(int i=1;i<n;i++){
        
        int l=0,h=i;
        int ind=0;
        while(h>=l){
          int mid=(l+h)/2;
          int sum= presum[i]- (mid>0?presum[mid-1]:0);
          int prev = (mid>0?val[mid-1]:0);
          if(sum>=prev){
            ind=mid;
            l=mid+1;
          }
          else h=mid-1;
        }
        if(ind==0){
          dp[i]=1;
          val[i]=presum[i];
        }
        else{
          dp[i]=dp[ind-1]+1;
          val[i]=presum[i]-presum[ind-1];
        }
     }
     cout<<dp.back();
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(ll n, ll m, vector<vector<string>>& c) {
    vector<vector<ll>> g1(n), g2(n);
    vector<ll> d1(n, 0), d2(n, 0);
    for (const auto& t : c) {
    if (t[0] == "x") {
    ll a = stoll(t[1]) - 1;
    ll b = stoll(t[2]) - 1;
    g1[a].push_back(b);
    d1[b]++;
    } else if (t[0] == "y") {
    ll a = stoll(t[1]) - 1;
    ll b = stoll(t[2]) - 1;
    g2[a].push_back(b);
    d2[b]++;
        }
    }

    auto ts = [&](vector<vector<ll>>& g, vector<ll>& d) -> vector<ll> {
    queue<ll> q;
    for (ll i = 0; i < n; i++) {
    if (d[i] == 0) q.push(i);
    }
    vector<ll> o;
    while (!q.empty()) {
    ll u = q.front();
    q.pop();
    o.push_back(u);
    for (ll v : g[u]) {
    d[v]--;
    if (d[v] == 0) q.push(v);
        }
        }
    return o.size() == n ? o : vector<ll>();
    };

    vector<ll> o1 = ts(g1, d1);
    vector<ll> o2 = ts(g2, d2);
    if (o1.empty() || o2.empty()) return -1;
    vector<ll> r(n, 0), cols(n, 0);
    for (ll i = 0; i < n; i++) {
    for (ll v : g1[o1[i]]) {
    r[v] = max(r[v], r[o1[i]] + 1);
    }
    }
    for (ll i = 0; i < n; i++) {
    for (ll v : g2[o2[i]]) {
    cols[v] = max(cols[v], cols[o2[i]] + 1);
        }
    }
    ll max_r = *max_element(r.begin(), r.end()) + 1;
    ll max_cols = *max_element(cols.begin(), cols.end()) + 1;
    return max_r + max_cols;
}
int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<string>> c(m, vector<string>(3));
    for (ll i = 0; i < m; i++) {
        cin >> c[i][0] >> c[i][1] >> c[i][2];
    }
    cout << solve(n, m, c) << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll maxcoins(ll A[], ll siz) {
    ll nums[siz + 2];
    ll n = 1;
    for (ll i = 0; i < siz; i++) {
    if (A[i] > 0) {
    nums[n] = A[i];
    n++;
    }
    }
    nums[0] = nums[n] = 1;
    n++;
    ll dp[n][n] = {};
    for (ll j = 2; j < n; j++) {
    for (ll left = 0; left < n - j; left++) {
    ll right = left + j;
    for (ll i = left + 1; i < right; i++) {
    if (left == 0 && right == n - 1)
    dp[left][right] = max(nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right], dp[left][right]);
    else
    dp[left][right] = max(nums[left] * nums[right] + dp[left][i] + dp[i][right], dp[left][right]);
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    ll T;
    cin >> T;
    for (ll t = 1; t <= T; t++) {
    ll siz;
    cin >> siz;
    ll A[siz];
    for (ll i = 0; i < siz; i++) {
    cin >> A[i];
    }
    ll ans = maxcoins(A, siz);
    cout << "#" << t << ans << endl;
    }

    return 0;
}

using namespace std;

#define ll long long

int main() {
    int numBombs;
    cin >> numBombs;

    vector<pair<int, int>> bombTimers(numBombs);
    for (int i = 0; i < numBombs; i++)
        cin >> bombTimers[i].first >> bombTimers[i].second;

    sort(bombTimers.begin(), bombTimers.end(), [](const auto &a, const auto &b) {
        return a.second < b.second;
    });

    ll currentTime = 0;
    for (int i = 0; i < numBombs; i++) {
        currentTime += bombTimers[i].first;
        if (currentTime > bombTimers[i].second) {
            cout << -1 << endl;
            return 0;
        }
    }

    cout << currentTime << endl;
    return 0;
}