#include "ricehub.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;
constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
int32_t besthub(int32_t n, int32_t L, int32_t X[], long long b) {
vector <int> v;
for (int i = 0; i < n; i++) v.pb(X[i]);
sort(all(v));
int l = 1, r = n, res = 1;
while (l <= r) {
int mid = (l + r) / 2;
multiset <int> le, ri;
int sl = 0, sr = 0;
auto add = [&](int x) {
le.insert(x);
sl += x;
auto it = le.end();
--it;
ri.insert(*it);
sr += *it;
sl -= *it;
le.erase(it);
if (le.size() < ri.size()) {
le.insert(*ri.begin());
sl += *ri.begin();
sr -= *ri.begin();
ri.erase(ri.begin());
}
};
auto med = [&]() -> int {
return *le.rbegin();
};
auto rem = [&](int x) {
if (x <= med()) {
sl -= x;
le.erase(le.find(x));
}
else {
sr -= x;
ri.erase(ri.find(x));
}
if (le.size() < ri.size()) {
le.insert(*ri.begin());
sl += *ri.begin();
sr -= *ri.begin();
ri.erase(ri.begin());
}
if (le.size() > ri.size() + 1) {
auto it = le.end();
--it;
ri.insert(*it);
sr += *it;
sl -= *it;
le.erase(it);
}
};
auto cst = [&]() -> int {
return sr - med() * ri.size() + med() * le.size() - sl;
};
for (int i = 0; i < mid; i++) {
add(v[i]);
}
int mn = cst();
for (int i = mid; i < n; i++) {
add(v[i]);
rem(v[i-mid]);
mn = min(mn, cst());
}
if (mn <= b) {
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
return res;
}
