#include "ricehub.h"
#include <cmath>
using namespace std;
bool poss(int len, long long budget, int *x, int n) {
long long cost = 0;
int a = 0;
int b = len - 1;
int mid = (a + b) / 2;
long long left = 0;
long long right = 0;
for (int i = a; i <= b; i++) {
cost += abs(x[i] - x[mid]);
}
left = mid - a;
right = b - mid;
if (cost <= budget) return true;
while (b + 1 < n) {
cost -= x[mid] - x[a];
cost += left * (x[mid + 1] - x[mid]);
cost -= right * (x[mid + 1] - x[mid]);
mid++;
a++;
b++;
cost += x[b] - x[mid];
if (cost <= budget) return true;
}
return false;
}
int besthub(int n, int l, int x[], long long budget) {
int a = 1;
int b = n;
int res = -1;
while (a <= b) {
int mid = (a + b) / 2;
if (poss(mid, budget, x, n)) {
res = mid;
a = mid + 1;
} else {
b = mid - 1;
}
}
return res;
}
