#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
int besthub(int R, int L, int X[], long long B){
if(R <= 5000){
ll maximum = 0;
for(ll pos = 0;pos < R;pos++){
ll Lptr = pos;
ll Rptr = pos;
ll curcost = 0;
while(Lptr > 0 && curcost + abs(X[pos] - X[Lptr - 1]) <= B){
curcost += abs(X[pos] - X[Lptr - 1]);
Lptr--;
}
while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
curcost += abs(X[pos] - X[Rptr + 1]);
Rptr++;
}
while(Rptr < R - 1 && abs(X[pos] - X[Lptr]) > abs(X[pos] - X[Rptr + 1])){
curcost -= abs(X[pos] - X[Lptr]);
curcost += abs(X[pos] - X[Rptr + 1]);
Lptr++;
Rptr++;
while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
curcost += abs(X[pos] - X[Rptr + 1]);
Rptr++;
}
}
maximum = max(maximum,Rptr - Lptr + 1);
}
return maximum;
}else{
ll maximum = 0;
ll Lptr = 0;
ll Rptr = 0;
ll curcost = 0;
while(Lptr > 0 && curcost + abs(X[0] - X[Lptr - 1]) <= B){
curcost += abs(X[0] - X[Lptr - 1]);
Lptr--;
}
while(Rptr < R - 1 && curcost + abs(X[0] - X[Rptr + 1]) <= B){
curcost += abs(X[0] - X[Rptr + 1]);
Rptr++;
}
maximum = max(maximum,Rptr - Lptr + 1);
for(ll pos = 1;pos < R;pos++){
if(Rptr >= pos){
curcost += ((pos - Lptr) * abs(X[pos] - X[pos - 1]));
curcost -= ((Rptr - pos + 1) * abs(X[pos] - X[pos - 1]));
}else{
curcost += ((pos - Lptr) * abs(X[pos] - X[pos - 1]));
while(Rptr < pos){
Rptr++;
curcost += abs(X[pos] - X[Rptr]);
}
}
while(Lptr < pos && curcost > B){
curcost -= abs(X[pos] - X[Lptr]);
Lptr++;
}
while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
curcost += abs(X[pos] - X[Rptr + 1]);
Rptr++;
}
while(Lptr + 1 <= pos && Rptr < R - 1 && abs(X[pos] - X[Lptr]) > abs(X[pos] - X[Rptr + 1])){
curcost -= abs(X[pos] - X[Lptr]);
curcost += abs(X[pos] - X[Rptr + 1]);
Lptr++;
Rptr++;
while(Rptr < R - 1 && curcost + abs(X[pos] - X[Rptr + 1]) <= B){
curcost += abs(X[pos] - X[Rptr + 1]);
Rptr++;
}
}
maximum = max(maximum,Rptr - Lptr + 1);
}
return maximum;
}
}
