#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N;
vector<ll> vals;
vector<ll> prefSum;
ll ans = 0;
int cost (int lb, int ub, int idx) {
return (prefSum[ub] - prefSum[idx]) - vals[idx]*(ub - idx) + vals[idx]*(idx + 1 - lb) - (prefSum[idx+1] - prefSum[lb]);
}
ll test (int idx, ll len) {
int lb = lower_bound(vals.begin(), vals.end(), vals[idx] - len) - vals.begin();
int ub = upper_bound(vals.begin(), vals.end(), vals[idx] + len) - vals.begin();
return cost(lb, ub, idx);
}
int besthub(int R, int L, int X[], long long B)
{
N = R;
vals.resize(N);
prefSum.assign(N+1, 0);
for (int i = 0; i < N; i++) {
vals[i] = X[i];
prefSum[i+1] = vals[i] + (i > 0 ? prefSum[i] : 0);
}
for (int idx = 0; idx < N; idx++) {
ll lo = 0, hi = L;
while (hi - lo > 1) {
int mid = lo + (hi - lo) / 2;
if (test(idx, mid) <= B) {
lo = mid;
}
else {
hi = mid;
}
}
ll lb = lower_bound(vals.begin(), vals.end(), vals[idx] - lo) - vals.begin();
ll ub = upper_bound(vals.begin(), vals.end(), vals[idx] + lo) - vals.begin();
ll numClose = (lb > 0 ? lb - (lower_bound(vals.begin(), vals.end(), vals[lb-1]) - vals.begin()) : 0);
ll len = (lb > 0 ? vals[idx] - vals[lb-1] : 1);
if (ub < N-1 && lb > 0 && vals[ub] - vals[idx] < vals[idx] - vals[lb-1]) {
numClose = 0;
}
if (ub < N-1 && (lb == 0 || vals[ub] - vals[idx] <= vals[idx] - vals[lb-1])) {
len = vals[ub] - vals[idx];
numClose += (ub < N-1 ? upper_bound(vals.begin(), vals.end(), vals[ub]) - vals.begin() - 1 - ub : 0);
}
ll res = ub - lb + min(numClose, ((B - cost(lb, ub, idx))/len)*len);
ans = max(ans, res);
}
return ans;
}
