#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
long long int typedef li;
//1-root obicnog, 2-root kurca
li val[10000007],L[10000007],R[10000007],idx=2;
void add(li p, li l, li r, li s, li x)
{
val[p]+=x;
if (l==r) return;
li mid=(l+r)/2;
if (s<=mid)
{
if (!L[p]) L[p]=++idx;
add(L[p],l,mid,s,x);
}
else
{
if (!R[p]) R[p]=++idx;
add(R[p],mid+1,r,s,x);
}
}
li sum(li p, li l, li r, li ll, li rr)
{
if (!p || ll>r || rr<l) return 0;
if (ll<=l && rr>=r) return val[p];
li mid=(l+r)/2;
return sum(L[p],l,mid,ll,rr)+sum(R[p],mid+1,r,ll,rr);
}
li walk(li p, li l, li r, li k)
{
if (l==r) return l;
li mid=(l+r)/2;
if (val[L[p]]>=k) return walk(L[p],l,mid,k);
return walk(R[p],mid+1,r,k-val[L[p]]);
}
li balans(li m)
{
if (m<=0) return 0;
li p=walk(1,1,1e18,m/2);
return ((li)sum(1,1,1e18,1,p)*p-(li)sum(2,1,1e18,1,p))+((li)sum(2,1,1e18,p,1e18)-(li)sum(1,1,1e18,p,1e18)*p);
}
int besthub(int n, int useless, int x[], li b)
{
li l=0,r=0,mx=0;
for (;r<n;r++)
{
add(1,1,1e18,x[r],1);
add(2,1,1e18,x[r],x[r]);
while (balans(r-l+2)>b) add(1,1,1e18,x[l],-1),add(2,1,1e18,x[l],-x[l]),l++;
//cout<<"["<<l<<","<<r<<"] - "<<balans(r-l+2)<<endl;
mx=max(mx,r-l+1);
}
return mx;
}
