#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
bool ok(int ask, int AllRice,int32_t X[],int budget){
if(ask==1)return 1;
int l=0,r=ask-1;
int m=l+(r-l)/2;
int sum=0;
int last=0;
int now;
for(int i=m-1;i>=0;--i){
now=X[i+1]-X[i];
sum+=now+last;
last=now;
}
last=0;
for(int i=m+1;i<=r;++i){
now=X[i]-X[i-1];
sum+=now+last;
last=now;
}
int LL = (m > l ? X[m]-X[m-1] : 0);
int RR = (m < r ? X[m+1]-X[m] : 0);
int Lc=m-l;
int Rc=r-m;
if(sum<=budget)return 1;
while(r < AllRice-1){
// cost of dropped store X[l] to old median X[m]
sum -= X[m] - X[l]; // X[l] was left of median, so cost = X[m]-X[l]
// cost of added store X[r+1] to old median X[m]
sum += X[r+1] - X[m]; // X[r+1] is right of median (array sorted)
++l; ++r;
int new_m = l + (r-l)/2;
// adjust all stores for median shift from X[m] to X[new_m]
// stores left of new median (count = new_m - l) get farther
// stores right of new median incl. itself (count = r - new_m) get closer
int dist = X[new_m] - X[m];
sum += (long long)(new_m - l) * dist;
sum -= (long long)(r - new_m) * dist;
m = new_m;
if(sum <= budget) return 1;
} return 0;
}
int32_t besthub(int32_t R, int32_t L, int32_t X[], long long B)
{
sort(X,X+R);
int l=1,r=R;
/*
int ans=0;
while(l<r){
int m=l+(r-l)/2;
if(ok(m,R,X)){
ans=m;
l=m+1;
}else{
r=m;
}
}
*/
int ans=0;
while(l <= r){
int m = l + (r - l) / 2;
if(ok(m, R, X, B)){
ans = m;
l = m + 1;
}
else r = m - 1;
}
return ans;
}
