#include "ricehub.h"
#include <iostream>
using namespace std;
#define ll long long
#define int ll
const int MAX = 1e5 + 7;
int n;
ll ar[MAX];
ll pfx[MAX];
ll budget;
int solve(int hub) //place a hub in ar[hub], calculate maximum amount of rice
{
int l1 = 1, r1 = hub;
while (l1 < r1)
{
int mid1 = (l1 + r1) / 2;
ll cost1 = (hub - mid1) * ar[hub] - (pfx[hub-1] - pfx[mid1 - 1]);
ll rt_cost = (pfx[n] - pfx[hub-1]) - (n - hub + 1) * ar[hub];
if (cost1 > budget) l1 = mid1 + 1;
else if (cost1 + rt_cost <= budget) r1 = mid1;
else
{
int l2 = hub, r2 = n;
while (l2 < r2)
{
int mid2 = (l2 + r2 + 1) / 2;
ll cost2 = (pfx[mid2] - pfx[hub-1]) - (mid2 - hub + 1) * ar[hub];
if (cost1 + cost2 <= budget) l2 = mid2;
else r2 = mid2 - 1;
}
if (ar[l2+1] - ar[hub] < ar[hub] - ar[mid1]) l1 = mid1 + 1;
else r1 = mid1;
}
}
ll cost1 = (hub - l1) * ar[hub] - (pfx[hub-1] - pfx[l1 - 1]);
int l2 = hub, r2 = n;
while (l2 < r2)
{
int mid2 = (l2 + r2 + 1) / 2;
ll cost2 = (pfx[mid2] - pfx[hub-1]) - (mid2 - hub + 1) * ar[hub];
if (cost1 + cost2 <= budget) l2 = mid2;
else r2 = mid2 - 1;
}
return l2 - l1 + 1;
}
int32_t besthub(int32_t R, int32_t L, int32_t X[], long long B)
{
n = R;
budget = B;
for (int i = 1; i <= R; ++i)
{
ar[i] = X[i-1];
pfx[i] = pfx[i-1] + X[i-1];
}
int res = 0;
for (int i = 1; i <= R; ++i)
{
//cerr << i << ": " << solve(i) << '\n';
res = max(res, solve(i));
}
return res;
}
