#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
const int MAXN = 100000;
int v[MAXN + 1];
long long sp[MAXN + 1];
long long getSum(int st, int dr) {
return sp[dr] - sp[st - 1];
}
long long calc(int st, int dr) {
int mij;
mij = (st + dr) / 2;//il pun in median, adica in v[mij]
return (long long)v[mij] * (mij - st + 1) - getSum(st, mij) + getSum(mij + 1, dr) - (long long)v[mij] * (dr - mij);
}
int besthub(int n, int L, int X[], long long b) {
//o sa aleg o subsecventa ca pozitiile sa fie cat mai apropiate
//si o sa pun rice hubul in median ca sa aiba distanta minima pana la toate
//si fac 2 pointers ca sa extind subsecventa
//O(n)
int i, j, rez;
for (i = 1; i <= n; i++) {
v[i] = X[i - 1];
sp[i] = sp[i - 1] + v[i];
}
j = 1;
rez = 0;
for (i = 1; i <= n; i++) {
while (j <= n && calc(i, j) <= b) {
j++;
}
if (j - i > rez) {
rez = j - i;
}
}
return rez;
}
