#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
int budget_handler;
int ricefield_count;
int len;
int arr[100001];
int summed_range(int left, int right) {
//
int median = arr[(left+right)/2];
int sm = 0;
for (int i=left; i<=right; i++) {
sm += abs(arr[i] - median);
}
// cout << "from " << left << " to " << right << " gives: " << sm << endl;
return sm;
}
int furthest_valid(int leftlock) {
int low = leftlock;
int high = ricefield_count;
int 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 (int i=0; i<R; i++) {
arr[i] = X[i];
}
int mx = 0;
for (int i=0; i<R; i++) {
int besthere = furthest_valid(i);
// cout << i << " : " << besthere << endl;
mx = max(mx, besthere-i+1);
}
return mx;
}
