#include <bits/stdc++.h>
#include <ricehub.h>
#define DEBUG 0
using namespace std;
int cost(int R, int X[], int mid, long long B) {
long long closest = 1e18, sum = 0;
int l, r, pos, ct = 0, ok;
for(int i = 0; i < R; i++) {
if(abs(X[i] - mid) < closest) {
closest = abs(X[i] - mid);
pos = i;
}
}
if(X[pos] <= mid) {
r = min(R - 1, pos + 1);
l = r - 1;
}
else {
l = max(0, pos - 1);
r = l + 1;
}
l = r - 1;
while(1) {
closest = 1e18;
if(l >= 0 && closest > abs(mid - X[l])) {
closest = abs(mid - X[l]);
ok = 0;
}
if(r < R && closest > abs(X[r] - mid)) {
closest = abs(X[r] - mid);
ok = 1;
}
if(sum + closest > B) {
return ct;
}
ct++;
sum += closest;
if(!ok) {
l--;
}
else {
r++;
}
}
return R;
}
int besthub(int R, int L, int X[], long long B) {
int l = 1, r = L, ans = 0, mid, cost1;
int l2, r2, mid2, pos2, cost2;
while(l <= r) {
mid = (l + r) / 2;
cost1 = cost(R, X, mid, B);
l2 = l + 1, r2 = r, pos2 = r;
while(l2 <= r2) {
mid2 = (l2 + r2) / 2;
if(cost1 == cost(R, X, mid2, B)) {
l2 = mid2 + 1;
}
else {
r2 = mid2 - 1;
pos2 = min(pos2, mid2);
}
}
cost2 = cost(R, X, pos2, B);
if(cost1 > cost2) {
r = mid - 1;
ans = max(ans, cost1);
}
else {
l = mid + 1;
ans = max(ans, cost2);
}
}
return ans;
}
