/**
* author: tourist
* created:
**/
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
int besthub(int n, int len, int a[], long long b) {
vector<long long> p(n + 1);
for (int i = 0; i < n; i++) {
p[i + 1] = a[i];
p[i + 1] += p[i];
}
auto rsum = [&](int l, int r) -> int64_t {
return p[r] - p[l - 1];
};
int ans = 1;
for (int i = 1; i <= n; i++) {
int low = i + 1, high = n, idx = -1;
while (low <= high) {
int mid = (low + high) >> 1, med = (i + mid) >> 1;
long long cost = int64_t(med - i + 1) * int64_t(a[med]) - rsum(i, med) + rsum(med + 1, mid) - int64_t(mid - med) * int64_t(a[med]);
if (cost <= b) {
idx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
ans = max(ans, idx - i + 1);
}
return ans;
}
