#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
long long pre[100005];
long long suf[100005];
int n;
/*struct segtree{
struct node{
int mx,sum;
node(int x=0){
mx=sum=x;
}
friend node operator+(node a,node b){
node c;
c.mx=max(a.mx,b.mx);
c.sum=a.sum+b.sum;
return c;
}
};
node info[400006];
void buildp(int st,int en,int i){
if(st==en)return void(info[i]=pre[st]);
int m=(st+en)/2;
buildp(st,m,i*2);
buildp(m+1,en,i*2+1);
info[i]=info[i*2]+info[i*2+1];
}
void builds(int st,int en,int i){
if(st==en)return void(info[i]=suf[st]);
int m=(st+en)/2;
builds(st,m,i*2);
builds(m+1,en,i*2+1);
info[i]=info[i*2]+info[i*2+1];
}
pair<int,node> f(int st,int en,int i,int l,int r,int k,int b){
if(st>r||en<l)return {-1,node()};
if(st>=l&&en<=r)return {,info[i]};
int m=(st+en)/2;
auto x=f(st,m,i*2,l,r,k,b);
if(x.first==0)
}
}*/
long long ar[100005];
long long cost(int m){
long long ans=LLONG_MAX;
for(int i=1;i+m-1<=n;i++){
int l=i,r=i+m-1;
int md=(l+r)/2;
long long cst=pre[r]-pre[md-1]-ar[md]*(r-md+1) + suf[l]-suf[md+1]-ar[md]*(md-l+1);
ans=min(ans,cst);
}
return ans;
}
int besthub(int R, int L, int X[], long long B)
{
n=R;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+X[i-1];
//cerr<<pre[i]<<" ";
}
//cerr<<"\n";
for(int i=n;i>=1;i--){
suf[i]=suf[i+1]+L-X[i-1];
//cerr<<suf[i]<<" ";
}
//cerr<<"\n";
for(int i=1;i<=n;i++)ar[i]=X[i-1];
int st=1,en=R,ans=0;
while(st<=en){
int m=(st+en)/2;
long long x=cost(m);
//cerr<<m<<" "<<x<<"\n";
if(x<=B){
st=m+1;
ans=m;
}else{
en=m-1;
}
}
return ans;
}
