#include "ricehub.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int besthub(int n, int N, int a[], ll x)
{
vector<ll> p(n + 1, 0);
for (int i = 0; i < n; i++)
p[i + 1] = p[i] + a[i];
auto chk = [&](int k) -> bool
{
for (int l = 0, r = k - 1; r < n; l++, r++)
{
int m = (l + r) >> 1;
ll left = a[m] * (m - l) - (p[m] - p[l]);
ll right = (p[r + 1] - p[m + 1]) - a[m] * (r - m);
if (left + right <= x)
return 1;
}
return 0;
};
int l = 0, r = n + 1;
while (r - l > 1)
{
int mid = (r + l) / 2;
chk(mid) ? (l = mid) : (r = mid);
}
return chk(r) ? r : l;
}
