#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Info{int l, r; ll cost;};
int besthub(int R, int L, int X[], long long B) {
const int n = R;
if (n <= 5000) {
int ans = 0;
for (int i = 0; i < n; ++i) {
int curr = 1;
ll rem = B;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
if (i-1>=0) pq.push({X[i]-X[i-1], i-1});
if (1+i<n) pq.push({X[1+i]-X[i], 1+i});
while (!pq.empty()) {
auto x = pq.top(); pq.pop();
if (x.first > rem) break;
curr++; rem -= x.first;
int add = 1;
if (x.second < i) {
add = -1;
}
x.second += add;
if (x.second >= 0 && x.second < n) {
pq.push({abs(X[x.second]-X[i]), x.second});
}
}
ans = max(ans, curr);
}
return ans;
}
vector<ll> pre(X, X+n);
for (int i = 1; i < n; ++i) pre[i] += pre[i-1];
auto sum = [](const vector<ll>& ps, int l, int r)->long long{
if (l > r) return 0LL;
ll ans = ps[r];
if (l > 0) ans -= ps[l-1];
return ans;
};
auto get = [&sum, &n](int A[], int idx, int l, int r, const vector<ll>& ps)->Info{
int lb = lower_bound(A, A+n, l) - A;
int ub = upper_bound(A, A+n, r) - A - 1;
int le = 1+idx-lb;
int g = ub-idx;
return Info{lb, ub, 1LL*A[idx]*le-sum(ps, lb, idx) + sum(ps, 1+idx, ub)-1LL*g*A[idx]};
};
auto getleft = [&sum, &n](int p, int l, int r, const vector<ll>& ps)->ll{
const int len = 1+r-l;
return 1LL*p*len-sum(ps, l, r);
};
auto getright = [&sum, &n](int p, int l, int r, const vector<ll>& ps)->ll{
const int len = 1+r-l;
return sum(ps, l, r)-1LL*p*len;
};
int ans = 1;
for (int i = 0; i < n; ++i) {
Info best{-1,-1,-1};
{
int low = 0, high = 1e9;
while (low <= high) {
int mid = low + ((high-low)/2);
Info x = get(X, i, X[i]-mid, X[i]+mid, pre);
if (x.cost <= B) {
low = 1+mid;
best = x;
} else {
high = mid-1;
}
}
}
assert(best.l != -1);
int len = 1+best.r-best.l, op1 = 0, op2 = 0;
ll rem = B - best.cost;
assert(rem >= 0);
{
int low = 0, high = best.l-1;
while (low <= high) {
int mid = (low+high) >> 1;
if (getleft(X[i], mid, best.l-1, pre) <= rem) {
high = mid-1;
op1 = best.l-mid;
} else {
low = 1+mid;
}
}
}
{
int low = best.r+1, high = n-1;
while (low <= high) {
int mid = (low+high) >> 1;
if (getright(X[i], best.r+1, mid, pre) <= rem) {
low = 1+mid;
op2 = mid-best.r;
} else {
high = mid-1;
}
}
}
ans = max(ans, len+max(op1, op2));
}
return ans;
}
