#include<bits/stdc++.h>
#include "ricehub.h"
using ll = long long;
using namespace std;
ll pre_sum[100002];
ll range_sum(ll lo, ll hi) {
if ( lo == 0) return pre_sum[hi];
return pre_sum[hi] - pre_sum[lo - 1];
}
int besthub(int R, int L, int X[], long long B){
ll lo, hi, mid, Lo, Hi, mid1, lo1, hi1, lo2, hi2, sum;
for (int i = 0; i < R; i ++) {
if ( i == 0) pre_sum[i] = X[i];
else pre_sum[i] = pre_sum[i - 1] + X[i];
}
ll s;
ll max_s = 0;
for (int i = 0; i < R; i ++) {
lo = 1;
hi = R + 1;
while ( lo < hi) {
mid = (lo + hi)/2;
lo1 = 0;
hi1 = 1e9 + 1;
while ( lo1 < hi1) {
mid1 = (lo1 + hi1)/2;
Lo = lower_bound(X, X + R, X[i] - mid1) - X;
Hi = upper_bound(X, X + R, X[i] + mid1) - X - 1;
if ( Hi - Lo + 1 < mid) lo1 = mid1 + 1;
else hi1 = mid1;
}
mid1 =lo1;
Lo = lower_bound(X, X + R, X[i] - mid1) - X;
Hi = upper_bound(X, X + R, X[i] + mid1) - X - 1;
// cout << mid1 << " " << Lo << " " << Hi << endl;
// cout << mid << " " << lo1 << endl;
sum =0 ;
lo1 = Lo;
hi1 = i;
lo2 = i;
hi2 = Hi;
sum = sum + (hi1 - lo1 + 1) * X[i] - range_sum(lo1, hi1);
sum = sum + range_sum(lo2, hi2) - (hi2 - lo2 + 1) * X[i];
s = hi2 - lo1 + 1 - mid;
s = s * lo1;
sum = sum - s;
// cout << sum << "RRR" << endl;
if ( sum <= B) lo = mid + 1;
else hi = mid;
}
// cout << lo << " DONE" << endl;
lo --;
max_s = max(max_s, lo);
}
return max_s;
}
