#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
const int MAX_N = 100;
struct MedianStructure {
set<pair<int, int> > data;
set<pair<int, int> >::iterator median;
long long sumdists;
MedianStructure() {
sumdists = 0LL;
median = data.end();
}
void moveMedian(int dir) {
sumdists -= dir * median->first;
if(dir == 1)
median++;
else
median--;
sumdists -= dir * median->first;
}
void insert(int val, int poz) {
pair<int, int> x = make_pair(val, poz);
data.insert(x);
if(data.size() == 1)
median = data.begin();
else if(x < *median) {
sumdists -= val;
if(data.size() % 2 == 0) moveMedian(-1);
} else {
sumdists += val;
if(data.size() % 2 == 1) moveMedian(+1);
}
}
void erase(int val, int poz) {
pair<int, int> x = make_pair(val, poz);
if(x < *median) {
sumdists += val;
data.erase(x);
if(data.size() % 2 == 1) moveMedian(1);
} else if(x > *median) {
sumdists -= val;
if(data.size() % 2 == 1) moveMedian(-1);
data.erase(x);
} else if(data.size() % 2 == 0) {
moveMedian(1);
data.erase(x);
sumdists += val;
} else {
moveMedian(-1);
data.erase(x);
sumdists -= val;
}
}
long long getmediansum() {
return sumdists - median->first * (1 - data.size() % 2);
}
};
int besthub(int R, int L, int X[], long long B) {
int l;
int rez = 1;
MedianStructure *med = new MedianStructure();
// X[l...r] works
l = 0;
for(int r = 0; r < R; ++r) {
med->insert(X[r], r);
while(l < r && med->getmediansum() > B) {
med->erase(X[l], l);
l++;
}
rez = max(rez, r - l + 1);
}
return rez;
}
