#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e3 + 10;
ll s[MAXN];
int besthub(int r, int l, int x[], ll b){
vector<ll> val(r + 1), d(r + 1);
for(int i=1; i<=r; i++){
d[i] = (ll) x[i - 1];
}
for(int i=1; i<=r; i++){
s[i] = s[i - 1] + d[i];
// cout << i << " " << s[i] << "\n";
}
ll ans = 0;
for(ll i=1; i<=r; i++){
val[0] = -1e18;
for(ll j=1; j<=r; j++){
val[j] = -(s[j - 1] - j * d[i]);
}
for(ll j=i; j<=r; j++){
ll cost = d[j] * (j - i + 1) - (s[j] - s[i - 1]) + (i + 1) * d[i] - s[i];
ll pos = lower_bound(val.begin(), val.end(), cost - b) - val.begin();
// cout << i << " " << j << " " << pos << "\n";
if(pos <= 0) continue;
ans = max(ans, j - pos + 1);
}
}
return ans;
}
