#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
bool can(int k, int R, long long B, const vector<int>& X, const vector<long long>& prefix) {
for (int i = 0; i + k - 1 < R; i++) {
int j = i + k - 1;
int mid = (i + j) / 2;
long long leftSum = (mid > 0 ? prefix[mid - 1] : 0LL) - (i > 0 ? prefix[i - 1] : 0LL);
long long rightSum = prefix[j] - prefix[mid];
int leftCount = mid - i;
int rightCount = j - mid;
long long leftCost = 1LL * X[mid] * leftCount - leftSum;
long long rightCost = rightSum - 1LL * X[mid] * rightCount;
long long totalCost = leftCost + rightCost;
if (totalCost <= B)
return true;
}
return false;
}
int besthub(int R, int L, int X_raw[], long long B) {
vector<int> X(X_raw, X_raw + R);
sort(X.begin(), X.end());
vector<long long> prefix(R);
prefix[0] = X[0];
for (int i = 1; i < R; i++) {
prefix[i] = prefix[i - 1] + X[i];
}
int low = 1, high = R, best = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (can(mid, R, B, X, prefix)) {
best = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return best;
}
