#include <bits/stdc++.h>
#include <ricehub.h>
#define DEBUG 0
using namespace std;
int cost(int n, int X[], int mid, long long B) {
deque <int> L, R;
for(int i = 0; i < n; i++) {
if(X[i] <= mid) {
L.push_front(mid - X[i]);
}
else {
R.push_back(X[i] - mid);
}
}
int i = 0, j = 0;
long long sum = 0;
while(i < L.size() && j < R.size()) {
if(L[i] <= R[j]) {
sum += L[i++];
}
else {
sum += R[j++];
}
if(sum > B) {
return i + j - 1;
}
}
while(i < L.size()) {
sum += L[i++];
if(sum > B) {
return i + j - 1;
}
}
while(j < R.size()) {
sum += R[j++];
if(sum > B) {
return i + j - 1;
}
}
return n;
}
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;
}
