#include "ricehub.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int besthub(int R, int L, int positions[], long long B){
int n = R;
//sort(positions.begin(), positions.end());
vector<ll> prefixSum(n, 0);
prefixSum[0] = positions[0];
for (int i = 1; i < n; ++i) {
prefixSum[i] = prefixSum[i - 1] + positions[i];
}
int maxRiceBags = 0;
int left = 0;
for (int right = 0; right < n; ++right) {
int median = left + (right - left) / 2;
// Calculate the left part cost
ll leftSum = median > 0 ? prefixSum[median - 1] - (left > 0 ? prefixSum[left - 1] : 0) : 0;
ll leftCost = (ll)(median - left) * positions[median] - leftSum;
// Calculate the right part cost
ll rightSum = prefixSum[right] - prefixSum[median];
ll rightCost = rightSum - (ll)(right - median) * positions[median];
ll currentCost = leftCost + rightCost;
while (currentCost > B && left <= median) {
left++;
median = left + (right - left) / 2;
// Recalculate the left part cost
leftSum = median > 0 ? prefixSum[median - 1] - (left > 0 ? prefixSum[left - 1] : 0) : 0;
leftCost = (ll)(median - left) * positions[median] - leftSum;
// Recalculate the right part cost
rightSum = prefixSum[right] - prefixSum[median];
rightCost = rightSum - (ll)(right - median) * positions[median];
currentCost = leftCost + rightCost;
}
maxRiceBags = max(maxRiceBags, right - left + 1);
}
return maxRiceBags;
}
