#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*a[m] - suml) + (sumr - numr*a[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]; }