#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e6 + 10;
inline pll operator+ (const pll& a, const pll& b) {
return {a.X + b.X, a.Y + b.Y};
}
int n;
vector<ll> vec;
namespace median {
pll fen[MAXN], tot = {0, 0};
inline void update(int ind, pll val) {
tot = tot + val;
for (++ind; ind < MAXN; ind += ind & -ind)
fen[ind] = fen[ind] + val;
}
inline pll query(int ind) {
pll ans = {0, 0};
for (++ind; ind > 0; ind -= ind & -ind)
ans = ans + fen[ind];
return ans;
}
inline ll median() {
int l = 0, r = int(vec.size()) - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (query(mid).Y < (tot.Y + 1) / 2) l = mid + 1;
else r = mid;
}
return l;
}
inline ll cost() {
int ind = median();
ll ans = 0;
pll e = query(ind);
ans += e.Y * vec[ind] - e.X;
e = tot + pll(-e.X, -e.Y);
ans += e.X - e.Y * vec[ind];
return ans;
}
}
int besthub(int R, int L, int X[], long long B) {
n = R;
for (int i = 0; i < n; i++)
vec.push_back(X[i]);
int ans = 0, l = 0;
for (int r = 0; r < n; r++) {
median::update(r, {vec[r], 1});
// cerr << l + 2 << sep << r + 2 << sep << median::cost() << endl;
// break;
while (median::cost() > B) {
median::update(l, {-vec[l], -1});
l++;
}
ans = max(ans, r - l + 1);
}
return ans;
}
