#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
int besthub(int n, int L, int X[], long long lim) {
int a[n+5];
for (int i = 0; i < n; i++) a[i+1] = X[i];
long long pref[n+5];
pref[0] = 0;
for (int i = 1; i <= n; i++) pref[i] = pref[i-1] + a[i];
auto get = [&](int l, int r) {
int m = (l+r)/2;
long long suml = pref[m]-pref[l-1];
int numl = m-l+1;
long long sumr = pref[r]-pref[m];
int numr = r-m;
long long res = (numl*m - suml) + (sumr - numr*m);
return res;
};
int ansl = -1;
int ansr = -1;
for (int i = 1; i <= n; i++){
int l = i; int r = n;
int id = -1;
while (l <= r) {
int mid = (l+r)/2;
if (get(i,mid) <= lim) {
id = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ansr - ansl <= id - i) {
ansr = id;
ansl = i;
}
}
int pos = (ansl+ansr)/2;
return a[pos];
}
