#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define lll __int128_t
#define ulll __uint128_t
#define ld long double
#define lld __float128
#define fi first
#define se second
#define mp make_pair
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U>
bool chmax(T &x, U v) {return (v > x)? x=v,1 : 0;}
template<typename T, typename U>
bool chmin(T &x, U v) {return (v < x)? x=v,1 : 0;}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #define DEBUG
#ifdef DEBUG
#define _main "\e[36m"
#define _reset "\e[39m\n"
template<typename T>
inline void __print(T x) {cerr << x;}
template<typename T, typename U>
inline void __print(pair<T,U> x)
{
cerr << "("; __print(x.fi); cerr << ", "; __print(x.se); cerr << ")";
}
inline void _print() {}
template<typename T, typename... U>
inline void _print(T x, U... y)
{
__print(x);
if(sizeof...(y)) cerr << ", ";
_print(y...);
}
template<typename T>
inline void _print_arr(T x) {__print(x);}
template<typename T, typename... U>
inline void _print_arr(T x, int size, U... len)
{
cerr << "[";
bool has = sizeof...(len);
for(int i = 0; i < size; i++)
{
if(i) cerr << "," << (has? "\n" : " ");
_print_arr(x[i], len...);
}
cerr << "]";
}
#define _source source_location::current()
#define debug_pref(a) cerr << _main << _source.file_name() << ":" << _source.line() << ":" << _source.column() << " [" << a << "]";
#define debug(a...) {debug_pref(#a); cerr << " = ["; _print(a); cerr << "]" << _reset;}
#define debug_arr(a, sz...) {debug_pref(#a); cerr << " = "; _print_arr(a, sz); cerr << _reset;}
#endif
#ifndef DEBUG
#define debug(a...)
#define debug_arr(a, sz...)
#endif
/*
dp[i][j] -> dp[j][k] + f(i,j,k)
lets fix j
dp[j][j] = max(dp[i][j] + f(i,j,j)) whats f(i, j, j)? its 1 if theres a suffix with sum a[j], 0 otherwise
so it will be 0 for larger values and might turn into 1 for smaller values
now lets do dp[j][j+1]. Same idea, but we have to update all values with f(i,j,j+1)-f(i,j,j).
Turns out this value is easy, its 1 if theres suffix of sum a[j]+a[j+1]
so this is really just a segment tree. For every (j, j') we want to know, if there's position i < j where sum(a[i] ... a[j-1]) = sum(a[j] ... a[j'])
this is of course easy with two pointers or something like that.
The problem is that segment tree will be too slow. Notice that we add these values only on a prefix, maybe theres a simpler solution then?
We can keep a pointer p, where sum(a[p]...a[j-1]) >= sum(a[j] ... a[k])
when we look at new value k, we move this pointer to the left until we have to. For every value dp[p][j-1] that we pass, we will add this dp as a constant
this value will not change for future k, so we keep maximum over all of these dp[p+][j-1]. As for values less, we need to know prefix maximum dp[p-][j-1], where
we'll also add the current added value from f(p,j,k). and thats it.
Im sceptical of these dp transitions though. After a careful look they do seem fine, after j we know that all dp states of form dp[j][k>=j] are calculated
so after we do that for all j, we find maximum in dp[j][n-1]
*/
const int MAXN = 5005;
int dp[MAXN][MAXN];
int prf[MAXN];
int main()
{
fast;
int n; cin >> n;
int a[n];
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
for(int i = 1; i <= n; i++)
{
dp[0][i] = 0;
}
dp[0][0] = -1e9;
for(int i = 1; i < n; i++)
{
prf[0] = -1e9;
for(int j = 0; j < i; j++)
{
prf[j+1] = max(prf[j], dp[j][i]);
}
int sum = 0, cur_sum = 0;
int p = i;
int add = 0;
pair<int, int> fixed_max = mp(-1e9, -1);
for(int j = i; j < n; j++)
{
dp[i][j+1] = max(fixed_max.fi, prf[p] + add);
sum += a[j];
while(p > 0 && cur_sum + a[p-1] <= sum)
{
cur_sum += a[p-1];
chmax(fixed_max, mp(dp[p-1][i] + add, p));
if(cur_sum == sum)
add++;
p--;
}
}
}
int ans = 0;
for(int i = 0; i < n; i++)
{
chmax(ans, dp[i][n]);
}
cout << ans;
}
/*
6
2 2 2 1 1 2
4
2 2 2 2
6
2 2 2 2 2 2
13
9 5 2 8 8 2 5 9 9 7 8 5 10
9 5 2 8
9 5 2 8
9 7 8 5 10
12
5 5 2 3 2 1 1 5 5 2 5 1
11
1 1 1 1 1 1 1 1 1 1 1
6
1 2 3 2 1 1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3
1 2 2
5
1 2 1 1 1
*/
