#include"ricehub.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[100005];
ll b,pref[100005],suff[100005];
ll pref_calc(ll l,ll r){
return pref[r]-(l-1)*(a[r]-a[l-1])-pref[l-1];
}
ll suff_calc(ll l,ll r){
return suff[l]-(n-r)*(a[r+1]-a[l])-suff[r+1];
}
bool app(ll l,ll r){
ll i=(l+r)>>1;
ll mn=pref_calc(l,i)+suff_calc(i,r);
return mn<=b;
}
bool check(int x){
bool flag=0;
for(int i=1;i+x-1<=n;i++)flag|=app(i,x+i-1);
return flag;
}
int besthub(int N,int L,int A[],ll B){
n=N;b=B;
for(int i=0;i<n;i++)a[i+1]=A[i];
for(int i=1;i<=n;i++)
pref[i]=pref[i-1]+(i-1)*(a[i]-a[i-1]);
for(int i=n;i>=1;i--)
suff[i]=suff[i+1]+(n-i)*(a[i+1]-a[i]);
int l=1,r=n,m;
while(l<r){
m=(l+r+1)>>1;
if(check(m))l=m;
else r=m-1;
}
return l;
}
//#include"grader.cpp"
