#include "ricehub.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
ll p[100005];
ll sum(int l,int r){
return p[r]-p[l-1];
}
int besthub(int n, int idk, int X[], long long b){
vector<ll>x(n+1,0);
for(int i=1;i<=n;i++)
x[i]=X[i-1];
for(int i=1;i<=n;i++)
p[i]=p[i-1]+x[i];
int l=0,r=n+1;
while(l+1<r){
int m=(l+r)/2;
ll mi=1e18;
for(int e=m;e<=n;e++){
int s=e-m+1;
int me=(s+e)/2;
ll val=x[me]*(me-s+1)-x[me]*(e-me+1);
// cout<<e<<' '<<x[me]<<endl;
// cout<<"fi "<<e<<' '<<val<<endl;
val+=sum(me,e)-sum(s,me);
// cout<<"se "<<e<<' '<<val<<endl;
mi=min(mi,val);
}
// cout<<"mid "<<m<<' '<<mi<<endl;
if(mi<=b) l=m;
else r=m;
}
return l;
}
