#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 BruteCheck (int K) {
for (int l = 1; l <= N - K + 1; ++ l ) {
int r = l + K - 1;
int j = l;
for (int P = V[l]; P <= V[r]; ++ P ) {
while (j <= r && V[j] <= P) ++ j;
-- j;
LL val = P * (2 * j + 2 - 2 * l - K) - 2 * sp[j] + sp[l-1] + sp[r];
if (val <= Budget)
{
cout << l << " " << r << " " << P << '\n';
return 1;
}
}
}
return 0;
}
bool Check (int K) {
int j = 1;
while (j < K && Sum(1, K, j) > Sum(1, K, j+1)) ++ j;
if (Sum(1, K, j) <= 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;
LL 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;
}
