#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
long long budget_handler;
long long ricefield_count;
long long len;
long long arr[100001];
long long pf[100001];
void pfcompute() {
pf[0] = arr[0];
for (long long i=1; i<ricefield_count; i++) {
pf[i] = arr[i] + pf[i-1];
}
}
long long pfq(long long a, long long b) {
if (a == 0) return pf[b];
return pf[b] - pf[a-1];
}
long long summed_range(long long left, long long right) {
//
long long median = (left+right)/2;
long long medscore = arr[median];
long long sm = 0;
// from left to median
long long countl = median - left;
long long suml = pfq(left, median-1);
sm += (countl * medscore) - suml;
// from median to right
long long countr = right - median + 1;
long long sumr = pfq(median, right);
sm += sumr - (countr * medscore);
return sm;
}
long long furthest_valid(long long leftlock) {
long long low = leftlock;
long long high = ricefield_count;
long long mid;
while (low + 1 < high) {
mid = (low + high) / 2;
if (summed_range(leftlock, mid) <= budget_handler) {
low = mid;
}
else {
high = mid;
}
}
if (high != ricefield_count) {
if (summed_range(leftlock, high) <= budget_handler) {
return high;
}
}
return low;
}
int besthub(int R, int L, int X[], long long B) {
budget_handler = B;
len = L;
ricefield_count = R;
for (long long i=0; i<R; i++) {
arr[i] = X[i];
}
pfcompute();
long long mx = 0;
for (long long i=0; i<R; i++) {
long long besthere = furthest_valid(i);
// cout << i << " : " << besthere << endl;
mx = max(mx, besthere-i+1);
}
return mx;
}
