#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int NMAX = 1e5 + 5;
int N;
int LgMax;
LL sp[NMAX];
int V[NMAX];
LL Budget;
LL Sum (int st, int dr, int j) {
LL ans = sp[dr] + sp[st-1] - 2 * sp[j];
LL semn = (2 * j + 2 - 2 * st - (dr - st + 1));
if (semn < 0) return ans + 1LL * (V[j+1]-1) * semn;
return ans + 1LL * V[j] * semn;
}
bool Check (int K) {
int j = 1;
LL Min = Sum(1, K, 1);
LL val;
for (; j <= K; ++ j )
if ((val = Sum(1, K, j)) <= Min) Min = val;
if (Min <= Budget) return 1;
for (int l = 2; l <= N - K + 1; ++ l ) {
int r = l + K - 1;
while (j < r && Sum(l, r, j) < Sum(l, r, j+1)) ++ j;
Min = Sum(l, r, j);
if (Min <= Budget) return 1;
}
return 0;
}
int besthub(int R, int L, int X[], long long B)
{
N = R, LgMax = L;
for (int i = 1; i <= N; ++ i )
V[i] = X[i-1];
for (int i = 1; i <= N; ++ i )
sp[i] = sp[i-1] + 1LL * V[i];
Budget = B;
int st = 1, dr = N;
int ans = 1;
while (st <= dr) {
int mij = (st + dr) >> 1;
if (Check(mij)) {
ans = mij;
st = mij + 1;
}
else dr = mij - 1;
}
return ans;
}
