#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int besthub(int R, int L, int X[], ll B)
{
vector<ll> v;
for(int i=0;i<R;i++){
v.push_back(X[i]);
}
vector<ll> sfx(R), pfx(R);
ll ans=1;
sfx[R-1]=L-v[R-1];
pfx[0]=v[0];
for(int i=1;i<R;i++)pfx[i]=pfx[i-1]+v[i];
for(int i=R-1;i>=0;i--)sfx[i]=sfx[i+1]+(L-v[i]);
for(int i=0;i<R;i++){
int l=0,r=L+1;
while(r-l>1){
ll d=(l+r)/2;
ll lb=lower_bound(v.begin(),v.end(),v[i]-d)-v.begin();
ll ub=upper_bound(v.begin(),v.end(),v[i]+d)-v.begin();
ll bel=sfx[lb] - sfx[i] - (i-lb)*(L-v[i]);
ll abv=pfx[ub-1]-pfx[i] - (ub-i-1)*v[i];
//~ printf("d is %lld, lb %lld ub %lld bel %lld abv %lld\n", d,lb,ub,bel,abv);
if(bel + abv > B){
r=d;
}
else {
l=d;
}
}
ll d=l;
ll lb=lower_bound(v.begin(),v.end(),v[i]-d)-v.begin();
ll ub=upper_bound(v.begin(),v.end(),v[i]+d)-v.begin();
ll bel=sfx[lb] - sfx[i] - (i-lb)*(L-v[i]);
ll abv=pfx[ub-1]-pfx[i] - (ub-i-1)*v[i];
assert(bel + abv <= B);
ll left=B-bel-abv;
ll nxt=min((lb == 0? 1e16 : v[i]-v[lb-1]), (ub == R ? 1e16:v[ub]-v[i]));
ll add=left/nxt;
ll cand=ub-lb+add;
ans=max(ans,cand);
}
return ans;
}
