#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");
typedef long long i64;
const int nmax = 1e5;
static i64 s[nmax + 1];
bool check (int n, int v[], i64 b, int x) {
for (int i = x; i <= n; ++ i) {
int y = (i - x + 1);
int mij = (y + i) / 2;
if (b >= s[i] - s[mij] - 1LL * (i - mij) * v[mij] + 1LL * (mij - y + 1) * v[mij] - (s[mij] - s[y - 1])) {
return 1;
}
}
return 0;
}
int besthub (int n, int l, int v[], i64 b) {
for (int i = 1; i <= n; ++ i)
s[i] = s[i - 1] + v[i - 1];
int n2;
for (n2 = 1; (n2 << 1) <= n; n2 <<= 1) {
}
int ans = 0;
for (int step = n2; step > 0; step >>= 1) {
if (ans + step <= n && check(n, v, b, ans + step))
ans += step;
}
return ans;
}
/*int k[5] = {1, 2, 10, 12, 14};
int main() {
cout << besthub(5, 20, k, 6) << "\n";
return 0;
}*/
