#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std ;
const int N = 1e5 + 7 ;
int n ;
vector<long long> coordinates , prefix;
long long limit ;
long long calc(int l , int r){
if(l>r)return 0ll;
return prefix[r] - (l?prefix[l-1]: 0) ;
}
long long sum_abs(int st , int en, long long x){
int delimeter = upper_bound(coordinates.begin() + st , coordinates.begin() + en +1 , x) - coordinates.begin() ;
delimeter-- ;
long long ret = 1ll * x * (delimeter - st + 1) - calc(st , delimeter)+ calc(delimeter+1 , en) - 1ll* (en-delimeter) * x ;
return ret ;
}
bool check(int l , int r){
int lo = -1 , hi =1e9 ;
long long ret = 1e17 ;
while(hi - lo > 1){
int mid = (lo+hi) /2 ;
long long get1 = sum_abs(l , r ,mid) ;
long long get2 = sum_abs(l , r , mid+1) ;
if(get1 > get2){
lo = mid ;
}
else {
hi = mid ;
}
}
ret = sum_abs(l , r , lo+1) ;
return ret <= limit ;
}
int besthub(int R, int L, int X[], long long B)
{
n = R ;
limit = B ;
int ans = 1 ;
for(int i= 0 ; i<R ; i++){
if(prefix.size()){
prefix.push_back(X[i] + prefix.back() );
}
else {
prefix.push_back(X[i]);
}
coordinates.push_back(X[i]) ;
}
int l = 0 , r = -1 ;
while(r< R-1 ){
r++ ;
while( !check(l , r) )l++ ;
ans = max(ans , r-l + 1) ;
}
return ans;
}
