#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
const int N = 1e5 + 5;
int pref[N];
vector<int> x;
int cost(int l, int r){
int idx = (l + r) / 2, centre = x[(l + r) / 2];
int sub = pref[idx], add = pref[r] - pref[idx];
if (l != 0) sub -= pref[l - 1];
return ((idx - l + 1) * centre - sub + add - (r - idx) * centre);
}
int besthub(int R, int L, int X[], long long B)
{
int l = 0, r = R + 1, s = 0;
for (int i = 0; i < R; i++){
x.push_back(X[i]);
s += X[i];
pref[i] = s;
}
pref[R] = pref[R - 1];
while (r - l > 1){
int m = (l + r) / 2;
int ans = 1e9;
for (int i = m - 1; i < R; i++){
ans = min(ans, cost(i - m + 1, i));
}
if (ans <= B) l = m;
else r = m;
}
return l;
}
