#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; int n = R - k + 1; for(int l = 0; l<n; l++){ int r = l + k - 1; int m = (k+l)/2; int x = 0; int y = 0; if(l != 0)x = pref[l-1]; if(m != 0)y = pref[m-1]; long long temp_wyn = (m - l + 1)*X[m] - (pref[m] - x); temp_wyn += (pref[r] - y) - (r - (m+1) + 1)*X[m]; min_wyn = min(min_wyn, temp_wyn); } if(min_wyn <= B)return true; else return false; } long long besthub(int R, int L, int X[], long long B){ if(B == 0)return 0; vector<long long>pref(R+7, 0); for(int i = 0; i<R; i++){ pref[i] += X[i]; if(i == 0)continue; pref[i] += pref[i-1]; } int l = 1; int r = R; int wyn = 0; while(l<=r){ int mid = (l+r)/2; if(check(mid, pref, X, R, B)){ l = mid + 1; wyn = max(wyn, mid); } else r = mid - 1; } return wyn; }