#include <bits/stdc++.h> using namespace std; #define all(a) (a).begin(),(a).end() using ll = long long; const ll N=1e5; ll pref[N+99]; ll n,L; long long B; vector<ll>V; bool f(ll k) { for(ll i=1;i<=n-k+1;i++) { ll srodek=(i+i+k-1)/2; long long srodek_w=V[srodek]; long long ans=0; ans+=(srodek_w)*(srodek-(i-1))-(pref[srodek]-pref[i-1]); // if(k==4) // { // cout << ans << " " << srodek_w << " " << srodek << " " << pref[srodek] <<" - " << pref[i-1]<< '\n'; // cout << srodek-(i-1) << '\n'; // } ans+=(pref[i+k-1]-pref[srodek])-(srodek_w)*(i+k-1-srodek); // if(k==4) // { // cout << ans << " " << pref[i+k-1] <<" - " << pref[srodek]<< '\n'; // cout << srodek_w << " * " <<i+k-1-srodek << '\n'; // } if(ans<=B)return 1; } return 0; } int besthub(int _R, int _L, int X[], long long _B){ B = _B; n = _R; L = _L; V.resize(n + 1); for(int i = 0; i < n; i++)V[i+1] = X[i]; //sort(all(V)); for(ll i=1;i<=n;i++) { pref[i]=pref[i-1]+V[i]; } // for(ll i=1;i<=n;i++) // { // cout << f(i)<<"X" << '\n'; // } ll l=1,r=n+1; while(r-l>1) { ll s=(l+r)/2; if(f(s))l=s; else r=s; } return l; }