#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, now;
// Bug 1 fixed: was i>=0, must be i>=l
for(int i=m-1; i>=l; --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;
}
// Bug 2&3 fixed: guard against out-of-bounds
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;
// Bug 4 fixed: was r < AllRice, must be r < AllRice-1
while(r < AllRice-1){
++r; ++l;
m=l+(r-l)/2;
// Bug 5 fixed: compute new gaps before using them,
// use OLD Lc/Rc for delta, then update counts
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)
{
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;
}
