define 6 2D arrays for DP:

RL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to right (when there are only 2 dots, or the i-th dot is on the left of j, and dist(i,j)<=dist(j,k), which is equivalent to, x[i]>=2*x[j]-x[k]).

LL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to left (when there are more than 2 dots, and the i-th dot is on the left of j, and dist(i,j)>dist(j,k), which is equivalent to, x[i]<2*x[j]-x[k]).

LL_cnt[j][k]: The number of sets which containing more than 2 dots, and the rightmost 2 dots are j, k, and j moves to left.

XX_sum[j][k]: sum(i=0...j)XX[j][k].

Then for each pair of (j, k) where j<k, we use binary search the smallest i0 that x[i0]>=2*x[j]-x[k] (if there's no such i0 then i0=j),then the DP formula is:

LL[j][k]=sum(i=i0...j-1)(RL[i][j]+LL[i][j])

RL[j][k]=1+sum(i=0...i0-1)(RL[i][j]+LL[i][j]+LL_cnt[i][j])

LL_cnt[j][k]=2^i0*(2^(j-i0)-1)

The final answer is sum(i=0...n-1, j=i+1...n-1)(RL[i][j]+LL[i][j]).

Dynamic programming, where the formula is

, which is equivalent to

$1$

where $$$sum[j]$$$ is the prefix sum of $$$a$$$. Then we can solve the problem by segment tree (since $$$sum[j]$$$ can be large, we need to sort $$$sum[j]$$$ first, and give them a new identifier from $$$0$$$ to $$$n-1$$$).

#include <bits/stdc++.h>

using namespace std;

char nl = '\n';
char sp = ' ';
using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using si = unordered_set<int>;
using sl = unordered_set<ll>;
using tsi = set<int>;
using tsl = set<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using tmii = map<int, int>;
using tmll = map<ll, ll>;
using mii = unordered_map<int, int>;
using mll = unordered_map<ll, ll>;
using pqi = priority_queue<int>;
using pqig = priority_queue<int, vi, greater<int>>;
using pql = priority_queue<ll>;
using pqlg = priority_queue<ll, vl, greater<ll>>;
using pqpii = priority_queue<pii>;
using pqpll = priority_queue<pll>;

#define tp3(T) tuple<T,T,T>
#define tp4(T) tuple<T,T,T,T>

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define outrange(x,min,max) ((x)<(min) || (x)>(max))

#define nano (chrono::system_clock::now().time_since_epoch().count())
#define second_since_start ((nano-start)/1e9)
#define init_rng mt19937 rng(nano)
#define randint(a,b) ((a)+rng()%((b)-(a)+1))

void yesno(bool a) {
	cout << (a ? "YES\n" : "NO\n");
}

template<typename L, typename R>
ostream& operator<<(ostream& out, const pair<L, R>& p) {
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, unordered_set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, unordered_map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

namespace segtree_single_point{
#define sti segtree<int>
#define stl segtree<ll>
	
	template<typename T>
	T lambda_add(T x,T y){
		return x+y;
	}
	
	template<typename T>
	T lambda_min(T x,T y){
		return x<y?x:y;
	}
	
	template<typename T>
	T lambda_max(T x,T y){
		return x>y?x:y;
	}
	
	template<typename T>
	class segtree{
	public:
		segtree(vector<T> &source, T (*merger)(T,T), T defaultValue=(T)0){
			this->merger=merger;
			this->defaultValue=defaultValue;
			int n=source.size();
			int L=1;
			while(L<n) L<<=1;
			size=L;
			vector<T> v(2*L,defaultValue);
			data=v;
			for(int i=0;i<n;i++) data[L+i]=source[i];
			for(int i=L-1;i>=1;i--) data[i]=merge(data[2*i],data[2*i+1]);
		}
		
		void add(int index,T value){
			put(index,data[size+index]+value);
		}
		
		void put(int index,T value){
			_put(size+index,value);
		}
		
		//查询闭区间[l,r]
		T query(int l,int r){
			return _query(0,size,l,r+1);
		}
		
		void show(){
			cout<<data;
		}
		
	private:
		vector<T> data;
		T (*merger) (T,T);
		int size;
		T defaultValue;
		
		T merge(T left,T right){
			return (*merger)(left,right);
		}
		
		void _put(int i,T value){
			data[i]=value;
			if(i==1) return;
			int j=i^1;
			if(i>j) swap(i,j);
			_put(i>>1,merge(data[i],data[j]));
		}
		
		T _query(int L,int R,int l,int r){
			if(L>=r || R<=l) return defaultValue;
			int index=(size+L)/(R-L);
			if(index>=size) {
				return data[index];
			}
			if(L>=l && R<=r) {
				return data[index];
			}
			int mid=(L+R)>>1;
			T ans=defaultValue;
			if(r>L) ans=merge(ans,_query(L,mid,l,r));
			if(l<R) ans=merge(ans,_query(mid,R,l,r));
			return ans;
		}
	};
}

using namespace segtree_single_point;

const int MAX=200005;
ll a[MAX];
ll sum[MAX];
int dp[MAX];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int _t=1;
//	cin>>_t;
	while(_t--){
		int n;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		sum[0]=a[0];
		for(int i=1;i<n;i++){
			sum[i]=sum[i-1]+a[i]; //prefix-sum
		}
		// assign the indexes of different values of sum[i] in the segment tree
		vl sums;
		for(int i=0;i<n;i++) sums.push_back(sum[i]);
		sort(all(sums));
		mll inv; // we use this map to find the index from a prefix-sum value
		for(int i=0;i<n;i++){
			if(i>0 && sums[i-1]==sums[i]) continue;
			inv[sums[i]]=i;
		}
		
		vi v(n);
		for(int i=0;i<n;i++) v[i]=-1e9;
		sti st(v,lambda_max,-1e9); // initialize the segment tree with size n and 
		//initial value -inf, query the range maximum
		dp[0]=(a[0]>=0)?1:0;
		st.put(inv[sum[0]],dp[0]);
		for(int i=1;i<n;i++){
			int index=inv[sum[i]];
			if(sum[i]>=0){
				dp[i]=i+1;
			}else{
				dp[i]=max(dp[i-1],i+st.query(0,index));
			}
			st.put(index,max(st.query(index,index),dp[i]-i));
		}
		cout<<dp[n-1];
	}
}