#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long a[N], pr[N];
long long ask(int l, int r){
if(l > r)
return 0;
return pr[r] - pr[l - 1];
}
bool ok(int x, long long y, int n){
for(int i = 1; i + x - 1 <= n; i++){
int l = i, r = i + x - 1;
int mid = (l + r) >> 1;
long long L = max(0, mid - l + 1) * a[mid] - ask(l, mid);
long long R = ask(mid, r) - max(0, r - mid + 1) * a[mid];
if(L + R <= y)
return true;
}
return false;
}
int besthub(int n, int x, int aa[], long long b){
for(int i = 0; i < n; i++)
a[i + 1] = aa[i];
for(int i = 1; i <= n; i++)
pr[i] = pr[i - 1] + a[i];
int l = 0, r = n;
int best = -1;
while(r >= l){
int mid = (l + r) >> 1;
if(ok(mid, b, n) == true){
best = mid;
l = mid + 1;
}
else r = mid - 1;
}
return best;
}
/*
5 20 6
1 2 10 12 14
*/
