#include "ricehub.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
int besthub(int n, int mx, int x[], long long b)
{
int l = 1, r = n + 1;
while(r - l > 1){
int mid = (r + l) / 2, sred = mid/2, last = 0;
ll sum = 0;
bool can = false;
for(int i = 0; i < mid; i++){
sum += abs(x[sred] - x[i]);
}
//cout << mid << " "<< sum << " Begin" << endl;
if(sum <= b) can = true;
for(int i = mid; i < n; i++){
sum -= abs(x[sred] - x[last]);
last++;
sum += (x[sred + 1] - x[sred]) * ((mid - 1) / 2);
sum -= (x[sred + 1] - x[sred]) * (mid / 2);
sred++;
sum += x[i] - x[sred];
if(sum <= b) can = true;
//cout << i << " "<< sum << endl;
}
//cout << can << " Here\n";
if(can) l = mid;
else r = mid;
}
return l;
}
//
// int main(){
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// int n, mx;
// ll b;
// cin >> n >> mx >> b;
// int x[n];
// for(int i = 0; i < n; i++){
// cin >> x[i];
// }
// cout << besthub(n, mx, x, b);
// return 0;
// }
