#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int> arr;
ll cost(int k) {
multiset<ll> s1, s2;
ll mnco = 1e18, su1=0, su2=0, mxl=0, mnr=0, med=0;
for(int i=1; i<=n; i++) {
if(i > k) {
if(s1.find(arr[i-k]) != s1.end()) {
s1.erase(s1.find(arr[i-k]));
su1 -= arr[i-k];
} else {
s2.erase(s2.find(arr[i-k]));
su2 -= arr[i-k];
}
}
if(s1.size() <= s2.size()) {
s1.insert(arr[i]);
su1 += arr[i];
} else {
s2.insert(arr[i]);
su2 += arr[i];
}
if(s1.size() && s2.size() && *s1.rbegin() > *s2.begin()) {
mxl = *s1.rbegin();
mnr = *s2.begin();
su1 += mnr - mxl;
su2 += mxl - mnr;
s1.insert(mnr);
s1.erase(s1.find(mxl));
s2.insert(mxl);
s2.erase(s2.find(mnr));
}
if(i > k-1) {
med = *s1.rbegin();
ll co = s1.size()*med - su1 + su2 - s2.size()*med;
mnco = min(mnco, co);
}
}
return mnco;
}
int besthub(int R, int L, int X[], long long B) {
n=R;
arr.assign(R+10, 0);
for(int i=1; i<=R; i++) {
arr[i] = X[i-1];
}
int l=1, r=R;
while(l < r) {
int mid = (l+r)/2;
if(cost(mid) > B) {
r = mid;
} else {
l = mid+1;
}
}
return l-1;
}
