#include "ricehub.h"
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <set>
#include <vector>
using namespace std;
class segment_tree {
public:
int siz = 1;
vector <int> segtree;
segment_tree() {}
void resize (int n) {
while (siz < n)
siz *= 2;
segtree.resize (2 * siz);
}
int get (int ind) {
int u = siz + ind - 1;
int ans = 0;
while (u)
ans += segtree[u] , u /= 2;
return ans;
}
void update (int L, int R, int K, int u, int l, int r) {
if (r < L || R < l)
return;
if (L <= l && r <= R) {
segtree[u] += K;
return;
}
const int m = (l + r) / 2;
update (L, R, K, 2 * u, l, m);
update (L, R, K, 2 * u + 1, m + 1, r);
}
void update (int L, int R, int K) {
return update (L, R, K, 1, 1, siz);
}
};
int besthub(int R, int L, int X[], long long B) {
segment_tree segtree;
segtree.resize (R + 1);
for (int i = 0; i < R; i++)
segtree.update (i, i, abs (X[i] - X[0]));
int l = 0, r = 0;
while (r < R && B - X[r] >= 0)
B -= X[r], r++;
int ans = r - l;
for (int i = 1; i < R; i++) {
// chooce rice hub
segtree.update (0, i - 1, X[i] - X[i - 1]);
segtree.update (i, segtree.siz, -(X[i] - X[i - 1]));
if (l <= i - 1)
B -= ((i - 1) - l + 1) * (X[i] - X[i - 1]);
if (r >= i)
B += (r - i + 1) * (X[i] - X[i - 1]);
while (B < 0) {
B += segtree.get (l);
l++;
}
while (r < R && segtree.get (l) > segtree.get (r)) {
B -= segtree.get (l);
l++;
B += segtree.get (r);
r++;
}
while (r < R && B >= segtree.get (r)) {
B -= segtree.get (r);
r++;
}
ans = max (r - l + 1, ans);
}
return ans;
}
