#include <ricehub.h>
using namespace std;
#define int long long
const int N = 3e5+5;
int x[N], pre[N];
int R, L, B;
int sm_ara(int l, int r){
auto it1 = lower_bound(x+1, x+R+1, l);
auto it2 = upper_bound(x+1, x+R+1, r); it2--;
int idx1 = it1 - x;
int idx2 = it2 - x;
return pre[idx2] - pre[idx1-1];
}
int cnt_ara(int l, int r){
auto it1 = lower_bound(x+1, x+R+1, l);
auto it2 = upper_bound(x+1, x+R+1, r);
return it2-it1;
}
int CNT(int p){
if(p < 1 or p > L) return 0;
// cout << p << endl;
int l = 1, r = R, ans = 0;
while(l <= r){
int mid = (l+r)/2;
int sayl = cnt_ara(p-mid+1, p);
int sayr = cnt_ara(p+1, p+mid-1);
int sml = sm_ara(p-mid+1, p);
int smr = sm_ara(p+1, p+mid-1);
int add = cnt_ara(p-mid, p-mid) + cnt_ara(p+mid, p+mid);
int 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(int i=1; i<=n; i++)
int besthub(int R, int L, int X[], int B){
for(int i=1; i<=R; i++) x[i] = X[i-1], pre[i] = pre[i-1] + x[i];
// cout << CNT(9) << endl;
// return;
int ans = 0;
for(int i=1; i<=R; i++) ans = max(ans, CNT(x[i]-1));
for(int 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();
// }
