#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll qs[100005];
int besthub(int R, int L, int X[], long long B)
{
n = R;
qs[0] = X[0];
for (int i = 1; i < n; i++) qs[i] += X[i] + qs[i - 1];
ll l = 0, r = n - 1;
ll cost = 1e18;
while (l < r) {
int mid = (l + r) / 2;
int idx = upper_bound(X, X + R, X[mid]) - X - 1;
ll cost = (idx - l + 1) * (X[mid]) - (qs[idx] - qs[l - 1]) + (qs[r] - qs[idx]) - (r - idx) * X[mid];
if (cost > B) {
if (X[mid]-X[l] > X[r]-X[mid]) l++;
else r--;
} else {
break;
}
}
while (l < r) {
int sz = ceil(1.0 * (l + r) / 2.0);
bool ok = 0;
for (int x = l; x + sz - 1 <= r; x++) {
int y = x + sz - 1;
int mid = (x + y) / 2;
ll cost = (mid - x + 1) * X[mid] - (qs[mid]-qs[l-1]) + (qs[r]-qs[mid]) - (r-mid) * X[mid];
if (cost <= B) ok = 1;
}
if (ok) l = sz;
else r = sz - 1;
}
return l;
}
