#include <bits/stdc++.h>
using namespace std;
#include "ricehub.h"
#define int long long
int prefix[100003], suffix[100003];
int r, l, pos[100003];
int b;
int costLeft(int x, int g, int d) {
int dst = x - pos[d];
dst *= (d - g + 1LL);
dst += suffix[g] - suffix[d+1] - (l - pos[d]) * (d - g + 1LL);
return dst;
}
int costRight(int x, int g, int d) {
int dst = pos[g] - x;
dst *= (d - g + 1LL);
dst += prefix[d] - prefix[g-1] - pos[g] * (d - g + 1LL);
return dst;
}
int cost(int g, int d) {
int x = pos[(g + d) / 2];
return costLeft(x, g, (g+d)/2) + costRight(x, (g+d)/2+1, d);
}
bool ok(int g, int d) {
return cost(g, d) < b;
}
int32_t besthub(int32_t R, int32_t L, int32_t *X, long long B) {
for(int i = 1; i <= R; i++) pos[i] = X[i-1];
r = R, l = L, b = B;
prefix[0] = suffix[R+1] = 0;
for(int i = 1; i <= R; i++)
prefix[i] = prefix[i-1] + pos[i];
for(int i = R; i >= 1; i--)
suffix[i] = suffix[i+1] + l - pos[i];
int ans = 1;
int j = -1;
for(int i = 1; i <= R; i++) {
if(j < i) {
j = i;
}
ans = max(ans, j-i+1);
while(j+1 <= R and ok(i, j+1)) {
ans = max(ans, (j+1-i+1));
j++;
}
}
return ans;
}
