#include "ricehub.h"
#include "bits/stdc++.h"
using namespace std;
int besthub(int R, int L, int X[], long long B)
{
vector<long long> pref(R);
long long curr = 0;
for (int i = 0; i < R; i++) {
curr += X[i];
pref[i] = curr;
}
auto compute = [&](int l, int r) -> long long {
if (r < 0) return 0ll;
long long res = pref[r];
if (l > 0) {
res -= pref[l - 1];
}
return res;
};
// int res = 0;
// for (int i = 0; i < R; i++) {
// for (int j = i; j < R; j++) {
// int mid = i + (j - i) / 2;
// int cntL = mid - i;
// int cntR = j - mid;
// long long cost = 1ll * cntL * X[mid] - compute(i, mid - 1);
// cost += compute(mid + 1, j) - 1ll * cntR * X[mid];
// if (cost <= B) {
// res = max(res, j - i + 1);
// }
// }
// }
int res = 0;
int l = 0, r = R;
while (l <= r) {
int mid = l + (r - l) / 2;
bool good = false;
for (int i = 0; i + mid <= R && !good; i++) {
int j = i + mid - 1;
int x = i + (j - i) / 2;
int cntL = x - i;
int cntR = j - x;
long long cost = 1ll * cntL * X[x] - compute(i, x - 1);
cost += compute(x + 1, j) - 1ll * cntR * X[x];
good |= cost <= B;
}
if (good) {
res = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
return res;
}
