#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long
const ll N = 3e5+5;
ll x[N], pre[N];
ll R, L, B;
ll sm_ara(ll l, ll r){
auto it1 = lower_bound(x+1, x+R+1, l);
auto it2 = upper_bound(x+1, x+R+1, r); it2--;
ll idx1 = it1 - x;
ll idx2 = it2 - x;
return pre[idx2] - pre[idx1-1];
}
ll cnt_ara(ll l, ll r){
auto it1 = lower_bound(x+1, x+R+1, l);
auto it2 = upper_bound(x+1, x+R+1, r);
return it2-it1;
}
ll CNT(ll p){
if(p < 1 or p > L) return 0;
// cout << p << endl;
ll l = 1, r = R, ans = 0;
while(l <= r){
ll mid = (l+r)/2;
ll sayl = cnt_ara(p-mid+1, p);
ll sayr = cnt_ara(p+1, p+mid-1);
ll sml = sm_ara(p-mid+1, p);
ll smr = sm_ara(p+1, p+mid-1);
ll add = cnt_ara(p-mid, p-mid) + cnt_ara(p+mid, p+mid);
ll sm = 0;
sm += smr - sayr * p;
sm += sayl * p - sml;
if(sm <= B){
add = min(add, (B-sm)/mid);
}
sm += add * mid;
if(sm <= B) ans = sayl + sayr + add, l = mid+1;
else r = mid-1;
}
return ans;
}
// for(ll i=1; i<=n; i++)
ll besthub(ll R, ll L, ll X[], ll B){
for(ll i=1; i<=R; i++) x[i] = X[i-1], pre[i] = pre[i-1] + x[i];
// cout << CNT(9) << endl;
// return;
ll ans = 0;
for(ll i=1; i<=R; i++) ans = max(ans, CNT(x[i]-1));
for(ll i=1; i<=R; i++) ans = max(ans, CNT(x[i]+1));
return ans;
}
// signed main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// solve();
// }
