#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
long long prefix[N + 5];
int besthub(int R, int L, int X[], long long B) {
for (int i = 1; i <= R; i++) prefix[i] = prefix[i - 1] + (long long)X[i - 1];
int l = 1, r = R, ans = 0;
while(l <= r) {
int m = (l + r)/2, valid = 0;
for (int i = m; i <= R; i++) {
int j = i - m + 1, median = (i + j)/2;
long long f = prefix[i] - prefix[median] - (long long)(i - median)*X[median - 1];
long long se = (long long)(median - j + 1)*X[median - 1] - (prefix[median] - prefix[j - 1]);
valid |= f + se <= B;
}
if (valid) ans = m, l = m + 1;
else r = m - 1;
}
return ans;
}
/*#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>
#define MAX_R 1000000
static int R, L;
static long long B;
static int X[MAX_R];
static int solution;
inline
void my_assert(int e) {if (!e) abort();}
static void read_input()
{
int i;
//my_assert(3==scanf("%d %d %lld",&R,&L,&B));
cin >> R >> L >> B;
for(i=0; i<R; i++)
// my_assert(1==scanf("%d",&X[i]));
cin >> X[i];
//my_assert(1==scanf("%d",&solution));
}
int main()
{
int ans;
read_input();
ans = besthub(R,L,X,B);
if(ans==solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d instead of %d.\n",ans,solution);
return 0;
}*/
