#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
int besthub(int R, int L, int X[], ll B) {
// possible to take x elements in B cost
auto check = [&](int x) -> bool {
if (x == 1) return true;
if (x == 2) {
for (int i = 1; i < R; i++) {
if (X[i] - X[i-1] <= B) return true;
}
return false;
}
ll best = LLONG_MAX, curr = 0;
int amt = x;
amt--;
deque<int> left, right;
int m = (amt + 1) / 2;
int med = X[m];
int ind = 0;
for (ind = 0; ind < m; ind++) left.push_back(X[ind]), curr += (med - X[ind]);
ind++; // take med
for (; ind < x; ind++) right.push_back(X[ind]), curr += (X[ind] - med);
best = min(best, curr);
// ensure ll later
for (int i = x; i < R; i++) {
curr -= (med - left.front()); left.pop_front();
left.push_back(med); med = right.front();
curr += (med - left.back()) * left.size();
curr -= (med - left.back()) * right.size();
right.pop_front(); right.push_back(X[i]);
curr += (X[i] - med);
best = min(best, curr);
}
return best <= B;
};
int l = 0, r = R;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m)) {
l = m;
} else {
r = m;
}
}
if (check(r)) l = r;
return l;
}
