#include <bits/stdc++.h>
using namespace std;
bool check(int k, vector<long long>& pref, int X[], int R, long long B){
long long min_wyn = LLONG_MAX;
long long n = R - k + 1;
for(long long l = 1; l <= n; l++){
long long r = l + k - 1;
long long m = ((l - 1) + (r - 1)) / 2; // mediana w X (0-based)
// LEWA strona
long long temp_wyn = 1LL * (m - (l - 1)) * X[m]
- (pref[m] - pref[l - 1]);
// PRAWA strona
// Uwaga: pref jest 1-based → sum(X[m+1 .. r-1]) = pref[r] - pref[m+1]
temp_wyn += (pref[r] - pref[m + 1])
- 1LL * (r - m - 1) * X[m];
min_wyn = min(min_wyn, temp_wyn);
}
return min_wyn <= B;
}
long long besthub(int R, int L, int X[], long long B){
if(B == 0) return 0;
// PREF MUSI MIEĆ DOKŁADNIE R+1 ELEMENTÓW
vector<long long> pref(R + 1, 0);
for(int i = 1; i <= R; i++)
pref[i] = pref[i - 1] + X[i - 1];
int l = 1, r = R, wyn = 0;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid, pref, X, R, B)){
wyn = mid;
l = mid + 1;
}
else r = mid - 1;
}
return wyn;
}
