#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template<typename T>
int len(T &a){return a.size();}
int besthub(int n, int lim, int a[], long long cost)
{
int ans = 0;
multiset<int> lef, rig;
ll sl = 0, sr = 0;
ll mon = 0;
auto add = [&](int x){
if(lef.empty() || *lef.rbegin() >= x){
lef.insert(x);
sl += x;
if(len(lef) - 1 >= len(rig) + 1){
int m = *lef.rbegin();
lef.erase(lef.find(m));
sl -= m;
rig.insert(m);
sr += m;
}
}else{
rig.insert(x);
sr += x;
if(len(rig) > len(lef)){
ll m = *rig.begin();
rig.erase(rig.begin());
sr -= m;
lef.insert(m);
sl += m;
}
}
if(lef.empty()) mon = 0;
else{
ll m = *lef.rbegin();
mon = m * len(lef) - sl + sr - m * len(rig);
}
};
auto rem = [&](int x){
if(x > *lef.rbegin()){
rig.erase(rig.find(x));
sr -= x;
if(len(lef) - 1 >= len(rig) + 1){
int m = *lef.rbegin();
lef.erase(lef.find(m));
sl -= m;
rig.erase(m);
sr += m;
}
}else{
lef.erase(lef.find(x));
sl -= x;
if(len(rig) > len(lef)){
ll m = *rig.begin();
rig.erase(rig.begin());
sr -= m;
lef.insert(m);
sl += m;
}
}
if(lef.empty()) mon = 0;
else{
ll m = *lef.rbegin();
mon = m * len(lef) - sl + sr - m * len(rig);
}
};
for(int l = 0, r = 0; r < n; r ++){
add(a[r]);
while(mon > cost){
rem(a[l]);
l ++;
}
if(mon <= cost) ans = max(ans, r - l + 1);
}
return ans;
}
