#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
int besthub(int n, int L, int X[], long long B){
vector<ll> pref(n);
pref[0]=X[0];
fall(i,1,n-1) pref[i]=pref[i-1]+X[i];
auto sum=[&](int a,int b){
if(a<0 || a>b) return 0ll;
ll r=pref[b];
if(a) r-=pref[a-1];
return r;
};
auto check=[&](int t){
fall(i,0,n-1){
int ini=max(0,t-n+i),fim=min(i,t-1);
ll us=ini; if(!ini) ini++;
while(ini<=fim){
int mei=(ini+fim)>>1;
if(X[i]-X[i-mei]<=X[i+t-mei-1]-X[i]) us=mei,ini=mei+1;
else fim=mei-1;
}
ll cur=X[i]*us-sum(i-us,i-1);
cur+=sum(i,i+t-us-1)-X[i]*(t-us);
if(cur<=B) return true;
}
return false;
};
int ini=1,fim=n,ans=0;
while(ini<=fim){
int mei=(ini+fim)>>1;
if(check(mei)) ans=mei,ini=mei+1;
else fim=mei-1;
}
return ans;
}
