#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<long long, long long>> a (1, {0, 0});
pair<long long, long long> pre[1000001];
struct khanhbang{
long long earn, cost, next_len;
inline khanhbang(){
earn = cost = 0;
next_len = 2e9;
}
};
khanhbang rice(int pos, int len){
int lo = 1, hi = pos, left = -1, right = -1;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if (pos - a[mid].first <= len) left = mid, hi = mid - 1;
else lo = mid + 1;
}
lo = pos, hi = n - 1;
while(lo <= hi){
int mid = (lo + hi) >> 1;
if (a[mid].first - pos <= len) right = mid, lo = mid + 1;
else hi = mid - 1;
}
khanhbang res;
res.earn = pre[right].second - pre[left - 1].second;
res.cost = (pre[pos].second - pre[left - 1].second) * pos - (pre[pos].first - pre[left - 1].first);
res.cost += (pre[right].first - pre[pos].first) - (pre[right].second - pre[pos].second) * pos;
if (left > 1) res.next_len = min(res.next_len, a[left - 1].first);
if (right < n - 1) res.next_len = min(res.next_len, a[right + 1].first);
return res;
}
long long besthub(int r, int l, int x[], long long b){
n = r;
long long res = 0;
int cnt = 1;
for (int i = 1; i < n; ++i){
if (x[i] != x[i - 1]){
a.push_back({x[i - 1], cnt});
cnt = 0;
}
cnt++;
}
a.push_back({x[n - 1], cnt});
n = a.size();
for (int i = 1; i < n; ++i){
pre[i].first = a[i].first + pre[i - 1].first;
pre[i].second = a[i].second + pre[i - 1].second;
}
for (int i = 1; i < n; ++i){
int lo = 0, hi = max(a[n - 1].first - a[i].first, a[i].first - a[1].first);
khanhbang ans;
while(lo <= hi){
int mid = (lo + hi) >> 1;
khanhbang k = rice(a[i].first, mid);
if (k.cost <= b) ans = k, lo = mid + 1;
else hi = mid - 1;
}
long long earn = ans.earn;
long long left = b - ans.cost;
if (ans.next_len != 2e9) earn += left / ans.next_len;
res = max(res, earn);
}
return res;
}
