#include<bits/stdc++.h>
#define ll long long int
#define ff first
#define ss second
#define FOR(i,N) for(i=0;i<N;i++)
#define FORe(i,N) for(i=1;i<=N;i++)
#define FORr (i,a,b) for(i=a;i<b;i++)
#define vi vector <ll>
#define ii pair<ll,ll>
#define vii vector<ii>
#define mp make_pair
#define pb push_back
#include "ricehub.h"
using namespace std;
/*
const ll MAXN = 1e5+ 4;
const ll LOGN = 17;
const ll ROOTN = 320;
const ll MOD = 1e9+7;
const ll INF = 1e17+8;
*/
long long cost(int N,int X[],int num)
{
//cout<<"getting in for num = "<<num<<endl;
ll i,j,k,sum = 0,ans;
FOR(i,num)
sum += X[i] - X[0];
ans = sum;
//cout<<"precomputed ans = "<<ans<<endl;
i = 0;
j = num - 1;
k = 1;
while(k < N)
{
//cout<<"entered while loop for i = "<<i<<"; j = "<<j<<"; k = "<<k<<endl;
sum += (k - i)*(X[k] - X[k-1]) - (j - k + 1)*(X[k] - X[k-1]);
if (k > j)
{
j++;
i++;
sum -= X[k]-X[i-1];
}
while(j < N-1 and i < k and (X[j+1] - X[k]) < (X[k] - X[i]))
{
sum += (X[j+1] - X[k]) - (X[k] - X[i]);
j++;
i++;
}
//cout<<"calculated sum = "<<sum<<endl;
ans = min(sum,ans);
k++;
}
return ans;
}
int besthub(int R,int L,int X[],long long B)
{
ll hi = R,lo = 1,mid = 0;
if (cost(R,X,R) <= B)
return R;
while(lo < hi-1)
{
mid = (hi+lo)/2;
if (cost(R,X,mid) > B)
hi = mid;
else
lo = mid;
}
return lo;
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll L,B,R;
cin>>R>>L;
ll i,X[R];
FOR(i,R)
cin>>X[i];
cin>>B;
cout<<besthub(R,L,X,B);
return 0;
}
*/
