#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
long long pos[100100], qs[100100];
long long cost_r(int i, int j)
{
if(i > j) return 0;
return qs[j] - qs[i] - pos[i]*(j-i);
}
long long cost_l(int i, int j)
{
return pos[j]*(j-i) - qs[j-1] + qs[i-1];
}
int solve_l(int i, long long bl)
{
int l = 1, r = i;
while(l != r)
{
int mid = (l+r)>>1;
if(cost_l(mid, i) <= bl) r = mid;
else l = mid+1;
}
return i-l;
}
int besthub(int R, int L, int X[], long long B)
{
int ans = 1;
for(int i=0 ; i<R ; i++)
{
pos[i+1] = X[i];
qs[i+1] = qs[i] + X[i];
}
for(int i=1 ; i<=R ; i++)
{
int l=i, r = R;
while(l != r)
{
int mid = (l+r+1)>>1;
long long br = cost_r(i, mid);
if(br > B)
{
r = mid-1;
continue ;
}
long long bl = B - br;
int hl = solve_l(i, bl);
if(mid - i + hl >= mid - 1 - i + solve_l(i, B - cost_r(i, mid-1))) l = mid;
else r = mid-1;
}
ans = max(ans, 1+l-i + solve_l(i, B - cost_r(i, l)));
}
return ans;
}
