#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);
for(int i=r-1; i>=0; i--){
x[i + 1] = x[i];
}
for(int i=1; i<=r; i++){
s[i] = s[i - 1] + x[i];
// cout << i << " " << s[i] << "\n";
}
int ans = 0;
for(int i=1; i<=r; i++){
val[0] = -1e18;
for(int j=1; j<=r; j++){
val[j] = -(s[j - 1] - j * x[i]);
}
for(int j=i; j<=r; j++){
ll cost = x[j] * (j - i + 1) - (s[j] - s[i - 1]) + (i + 1) * x[i] - s[i];
int 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;
}
