#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
int besthub(int n, int troll, int vec[], long long B){
int l,r;
int med;
ll val;
auto ini=[&](int x)->void{
l=0;
r=x-1;
med=vec[(l+r)/2];
val=0;
L(i,l,r)val+=abs(med-vec[i]);
};
auto upd=[&]()->void{
val-=abs(vec[l]-med);
l++;
r++;
int nmed=vec[(l+r)/2];
val+=(nmed-med)*((l+r)/2-l);
val-=(nmed-med)*(r-(l+r)/2);
val+=abs(vec[r]-nmed);
med=nmed;
};
auto testa=[&](int m)->bool{
ini(m);
int resp=val;
while(r!=n-1){
upd();
resp=val;
}
return resp<=B;
};
int lo=1, hi=n;
int resp=1;
while(lo<=hi){
int m=(lo+hi)/2;
if(testa(m)){
lo=m+1;
resp=m;
}
else hi=m-1;
}
return resp;
}
