//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#include "ricehub.h"
#include <cstdio>
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define all(a) a.begin() , a.end()
const long long mod = 1000000007;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>indexed_multiset;
bool valid (int n , int k , int a[] , long long t)
{
multiset<int> l , r;
long long sum1 = 0 , sum2 = 0;
for(int i = 0 ; i < n ; i++)
{
if(i >= k)
{
if(l.find(a[i - k]) != l.end())
{
l.erase(l.find(a[i - k]));
sum1 -= a[i - k];
}
else
{
r.erase(r.find(a[i - k]));
sum2 -= a[i - k];
}
}
if(l.size() <= r.size())
{
l.insert(a[i]);
sum1 += a[i];
}
else
{
r.insert(a[i]);
sum2 += a[i];
}
if(l.size() > 0 && r.size() > 0 && *l.rbegin() > *r.begin())
{
sum1 += (*r.begin() - *l.rbegin());
sum2 += (*l.rbegin() - *r.begin());
l.insert(*r.begin());
r.insert(*l.rbegin());
r.erase(r.begin());
l.erase(l.find(*l.rbegin()));
}
if(i >= k - 1 && (l.size() * *l.rbegin() - sum1) + (sum2 - *l.rbegin() * r.size()) <= t)
return 1;
}
return 0;
}
int besthub(int r , int l , int a[] , long long b)
{
long long st = 1 , en = r;
int ans = 1;
while(st <= en)
{
long long mid = (st + en) / 2;
if(valid(r , mid , a , b))
st = mid + 1 , ans = mid;
else
en = mid - 1;
}
return ans;
}
