#include <bits/stdc++.h>
#include "ricehub.h"
#define MAX_R 100000
#define MAX_N 100000
using namespace std;
typedef long long lint;
int n;
lint v[MAX_N + 1];
lint sum[MAX_N + 1];
lint bani;
bool pos(int len)
{
// cout << " INTRA LEN " << len << "\n";
// cout << sum[n] << "\n";
for(int i = len; i <= n; i ++)
{
int st = i - len + 1;
int med = ((len + 1) >> 1);
int p = st - 1 + med;
// cout << " SPRE ST AVEM " << med * v[p] << " - " << (sum[p] - sum[st - 1]) << "\n";
// cout << " SPRE DR AVEM " << (sum[i] - sum[p]) << " - " << (i - med) * v[p] << "\n";
lint cost = med * v[p] - (sum[p] - sum[st - 1]) +
(sum[i] - sum[p]) - (i - p) * v[p];
// if(len <= 4)
//cout << " SUNTEM " << st << " " << p << " " << i << " len " << len << " COSt " << cost << "\n";
if(cost <= bani)
return 1;
}
return 0;
}
int cautBin()
{
int i = 0;
int pas = 1 << 16;
while(pas != 0)
{
if(i + pas <= n && pos(i + pas) == 1)
i += pas;
pas >>= 1;
}
return i;
}
int besthub(int R, int L, int X[], long long B)
{
bani = B;
n = R;
sum[1] = X[0];
v[1] = X[0];
for(int i = 2; i <= n; i ++)
{
v[i] = X[i - 1];
sum[i] = sum[i - 1] + v[i];
}
int rez = cautBin();
return rez;
}
