#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) (x).size()
namespace {
const int nmax = 1e5 + 5;
const ll inf = 2e15 + 10;
const double A = 0.38196601125, B = 1 - A;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using tiii = tuple<int,int,int,ll>;
int n;
int X[nmax];
ll sum[nmax];
#define sum (sum + 1)
}
ll get(int l, int mid, int r) {
int ptrr = upper_bound(X, X + n, mid) - X;
int ptrl = ptrr - 1;
return (ll)(ptrl - l + 1) * mid - (sum[ptrl] - sum[l - 1]) + (sum[r] - sum[ptrr - 1]) - (ll)(r - ptrr + 1) * mid;
}
ll get(int l, int r) {
if(l >= n || r >= n) return inf;
int cl = X[l], cr = X[r];
int ccl = B * (double)cl + A * (double)cr;
int ccr = A * (double)cl + B * (double)cr;
ll vl = get(l, ccl, r), vr = get(l, ccr, r);
while(cr - cl > 4) {
if(vl > vr) {
cl = ccl;
vl = vr;
ccl = ccr;
ccr = A * (double)cl + B * (double)cr;
vr = get(l, ccr, r);
}
else {
cr = ccr;
vr = vl;
ccr = ccl;
ccl = B * (double)cl + A * (double)cr;
vl = get(l, ccl, r);
}
}
ll mn = get(l, cl, r);
for(int i = cl + 1; i <= cr; i++)
mn = min(mn, get(l, i, r));
return mn;
}
int besthub(int N, int vmx, int XX[], long long lim) {
{ // rename
n = N;
for(int j = 0; j < n; j++)
X[j] = XX[j];
}
{ // spart
for(int i = 0; i < n; i++) {
sum[i] = sum[i - 1] + X[i];
}
sum[n] = sum[n - 1];
sum[n + 1] = sum[n - 1];
}
int r = 0;
int mx = 0;
for(int l = 0; l < n; l++) {
r = max(l, r);
while(get(l, r) <= lim)
r++;
r--;
mx = max(mx, r - l + 1);
}
return mx;
}
