#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ALL(arr) begin(arr), end(arr)
#define CONTAINS(arr, val) (find(ALL(arr), val) == end(arr))
typedef pair<int, int> ii;
int besthub(int R, int L, int X[], long long B)
{
vector<int> linv;
vector<int> rinv;
stack<int> removed;
int cost = 0;
int ci = 1;
int best = 0;
for (int i = 0; i < R; i++) {
ci = max(ci, i+1);
int x = X[i];
if (i > 0) {
linv.push_back(X[i-1]);
cost += linv.size() * (X[i] - X[i-1]);
cost -= rinv.size() * (X[i] - X[i-1]);
if (rinv.size()) rinv.erase(rinv.begin());
if (X[i] == X[i-1]) continue;
}
while (cost > B) {
cost -= x - linv[0];
removed.push(linv[0]);
linv.erase(linv.begin());
}
while (ci < R && cost + X[ci] - x <= B) {
cost += X[ci] - x;
rinv.push_back(X[ci]);
ci++;
}
while (ci < R && linv.size() && x - linv[0] >= X[ci] - x) {
cost -= x - linv[0];
cost += X[ci] - x;
removed.push(linv[0]);
linv.erase(linv.begin());
rinv.push_back(X[ci]);
ci++;
}
while (ci < R && cost + X[ci] - x <= B) {
cost += X[ci] - x;
rinv.push_back(X[ci]);
ci++;
}
while (!removed.empty() && x - removed.top() <= B - cost) {
cost += x - removed.top();
linv.insert(linv.begin(), removed.top());
removed.pop();
}
best = max(best, (int)(linv.size() + rinv.size() + 1));
}
return best;
}
