#include <bits/stdc++.h>
using namespace std;
bool possible(int r, int amountOfHub , const int* x,long long b) {
int bestHub = 0;
int bestHubCount = 0;
int count = 0;
for (int i = 1; i < amountOfHub; i++)
count += x[i] - x[0];
bestHubCount = count;
for (int i = 1; i < amountOfHub; i++) {
int newCount = count+ (x[i] - x[i-1]) * (2*i-1-amountOfHub);
if (newCount >= count) {
bestHub = i-1;
bestHubCount = count;
break;
}
count = newCount;
}
if (bestHubCount <= b)
return true;
for (int i = 0; i < r-amountOfHub; i++) {
int currentHub = bestHub;
int currentCount = bestHubCount - x[bestHub] * 2 - x[i] + x[i+amountOfHub];
for (int j = currentHub-i; j < i + 1 +amountOfHub; j++) {
int newCount = count + (x[j]-x[j-1]) * (2*(j-i-1) - 1 - amountOfHub);
if (newCount >= count) {
bestHub = j-1;
bestHubCount = currentCount;
break;
}
currentCount = newCount;
}
if (bestHubCount <= b)
return true;
}
return false;
}
int besthub (int r, int, int* x,long long B) {
int begin = 0,end = r;
while (end - begin > 1) {
int mid = (end+begin)/2;
if (possible(r,mid,x,B))
begin = mid;
else
end = mid;
}
if (possible(r,end,x,B))
return end;
return begin;
}
#if 0
int main() {
int r,l,b;
cin >> r >> l >> b;
vector<int> vec(r);
for (int& v : vec) cin >> v;
cout << besthub(r,l,vec.data(),b);
}
#endif
