#include "ricehub.h"
#include <algorithm>
#define MAXN 100000
int cnt;
long long sum[MAXN + 1];
inline long long f(int p, int k, int n, int X[]) {
int rez = p;
for (int pas = 1 << 16; pas; pas >>= 1)
if (rez + pas <= n && X[rez + pas] <= X[p] + k)
rez += pas;
long long ans = sum[rez] - sum[p - 1] - 1LL * (rez - p + 1) * X[p];
cnt = rez - p + 1;
rez = p;
for (int pas = 1 << 16; pas; pas >>= 1)
if (rez - pas > 0 && X[rez - pas] >= X[p] - k)
rez -= pas;
cnt += p - rez;
ans += 1LL * (p - rez) * X[p] - (sum[p - 1] - sum[rez - 1]);
return ans;
}
inline int solve(int p, long long B, int n, int X[]) {
int rez = -1, cati = 0;
for (int pas = 1 << 29; pas; pas >>= 1)
if (f(p, rez + pas, n, X) <= B)
rez += pas, cati = cnt;
if (cati == n)
return cati;
return cati + (B - f(p, rez, n, X)) / (rez + 1);
}
int besthub(int R, int L, int X[], long long B) {
for (int i = R; i > 0; i--)
X[i] = X[i - 1];
for (int i = 1; i <= R; i++)
sum[i] = sum[i - 1] + X[i];
int ans = 0;
for (int i = 1; i <= R; i++)
ans = std::max(ans, solve(i, B, R, X));
return ans;
}
