#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;
// ❌ BUG: loop should start from m-1 down to l (not 0)
for(int i=m-1;i>=l;--i){ // FIX
now=X[i+1]-X[i];
sum+=now+last;
last=now;
}
last=0;
// ✅ this part is fine
for(int i=m+1;i<=r;++i){
now=X[i]-X[i-1];
sum+=now+last;
last=now;
}
// ❌ BUG: m-1 might be out of bounds when m == l
int LL = (m > l ? X[m]-X[m-1] : 0); // FIX
// ❌ BUG: m+1 might be out of bounds when m == r
int RR = (m < r ? X[m+1]-X[m] : 0); // FIX
int Lc=m-l;
int Rc=r-m;
if(sum<=budget)return 1;
// ❌ BUG: should be r < AllRice - 1
while(r < AllRice-1){ // FIX
++r;
++l;
m=l+(r-l)/2;
// ❌ BUG: LL and RR are never updated → WRONG
int newLL = (m > l ? X[m]-X[m-1] : 0); // FIX
int newRR = (m < r ? X[m+1]-X[m] : 0); // FIX
sum += (newLL - LL) * Lc; // FIX (use newLL)
sum += (newRR - RR) * Rc; // FIX (use newRR)
LL = newLL; // FIX
RR = newRR; // FIX
Lc = m - l; // FIX (must update counts)
Rc = r - m; // FIX
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;
}
