#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 1e5 + 5;
int n;
int a[N];
multiset <int> mtslo, mtshi;
ll sumlo, sumhi;
int median(){
return mtslo.empty() ? INT_MAX : *mtslo.rbegin();
}
ll cal_dist(){
int m = median();
return sumhi - (ll)m * isz(mtshi) + (ll)m * isz(mtslo) - sumlo;
}
void balance(){
while (isz(mtslo) > isz(mtshi) + 1){
int x = *mtslo.rbegin();
mtslo.erase(mtslo.find(x));
sumlo -= x;
mtshi.insert(x);
sumhi += x;
}
while (isz(mtslo) < isz(mtshi)){
int x = *mtshi.begin();
mtshi.erase(mtshi.find(x));
sumhi -= x;
mtslo.insert(x);
sumlo += x;
}
}
void insert(int x){
if (x <= median()){
mtslo.insert(x);
sumlo += x;
}
else{
mtshi.insert(x);
sumhi += x;
}
balance();
}
void erase(int x){
if (mtslo.find(x) != mtslo.end()){
mtslo.erase(mtslo.find(x));
sumlo -= x;
}
else{
mtshi.erase(mtshi.find(x));
sumhi -= x;
}
balance();
}
int besthub(int _n, int l, int _a[], ll val){
n = _n;
For(i, 0, n){
a[i] = _a[i];
}
int ans = 0;
int r = -1;
For(l, 0, n){
while (r + 1 < n){
r++;
insert(a[r]);
if (cal_dist() > val){
erase(a[r]);
r--;
break;
}
}
ans = max(ans, r - l + 1);
erase(a[l]);
}
return ans;
}
/*
==================================================+
INPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
