#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==0)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){
++l;++r;
m=l+(r-l)/2;
// cout<<l<<' '<<r<<'\n';
int newLL = (m > l ? X[m]-X[m-1] : 0);
int newRR = (m < r ? X[m+1]-X[m] : 0);
sum+=(newLL-LL)*Lc;
sum+=(newRR-RR)*Rc;
LL=newLL;
RR=newRR;
Lc=m-l;
Rc=r-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;
}
