#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll sum[maxn];
bool check(int n, int l, const vector<int> &v, ll b, int k){
for(int i=k-1; i<n; i++){
int j = i - k + 1;
int meio = (i + j) >> 1;
ll val = sum[i] - sum[meio] - v[meio] * (i-meio);
val += -sum[meio] + (j == 0 ? 0 : sum[j-1]) + v[meio] * (meio - j + 1);
if(val <= b) return true;
}
return false;
}
int besthub(int n, int l, int x[], ll b){
vector<int> v(n);
for(int i=0; i<n; i++) v[i] = x[i];
sum[0] = v[0];
for(int i=1; i<n; i++) sum[i] = v[i] + sum[i-1];
int ini = 1, meio, fim = n, ans = 1;
while(ini <= fim){
meio = (ini + fim) >> 1;
if(check(n, l, v, b, meio)){
ans = meio;
ini = meio + 1;
}
else fim = meio - 1;
}
return ans;
}
