#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<ll, ll> segm[400005];
int pospos[100005], atar[100005];
int D, ST, N;
int sl=0, sr=-1;
void upd(int idx, int l, int r, int tgt, pair<int, int> val) {
if(l==r) {
segm[idx].first += val.first;
segm[idx].second += val.second;
return;
}
int mid = (l+r)>>1;
if(tgt <= mid) upd(idx*2+1, l, mid, tgt, val);
else upd(idx*2+2, mid+1, r, tgt, val);
segm[idx].first = segm[idx*2+1].first + segm[idx*2+2].first;
segm[idx].second = segm[idx*2+1].second + segm[idx*2+2].second;
}
ll qr(int idx, int l, int r, int k) {
if(segm[idx].first <= k) return segm[idx].second;
int mid = (l+r)>>1;
if(segm[idx*2+2].first >= k) return qr(idx*2+2, mid+1, r, k);
return qr(idx*2+1, l, mid, k-segm[idx*2+2].first) + segm[idx*2+2].second;
}
ll getmxbet(int cnt) {
if(cnt <= 0) return 0;
return qr(0, 0, N-1, cnt);
}
ll cbans=0;
void setdpup(int l, int r) {
while(l<sl) {sl--; upd(0, 0, N-1, pospos[sl], {1, atar[sl]});}
while(sr<r) {sr++; upd(0, 0, N-1, pospos[sr], {1, atar[sr]});}
while(sl<l) {upd(0, 0, N-1, pospos[sl], {-1, -atar[sl]}); sl++;}
while(r<sr) {upd(0, 0, N-1, pospos[sr], {-1, -atar[sr]}); sr--;}
}
queue<pair<pair<int, int>, pair<int, int>>> Q;
void rundp1(int l, int r, int posl, int posr) {
if(l>r) return;
int mid = (l+r)/2;
setdpup(mid, max(posl, mid));
pair<ll, ll> bestans(getmxbet(D-ST-max(posl,mid)+2*mid), max(posl, mid));
for(int i=max(posl, mid)+1; i<=posr; i++) {
setdpup(mid, i);
bestans = max(bestans, {getmxbet(D-ST-i+2*mid), i});
}
cbans = max(cbans, bestans.first);
Q.push({{l, mid-1}, {posl, bestans.second}});
Q.push({{mid+1, r}, {bestans.second, posr}});
}
void rundp2(int l, int r, int posl, int posr) {
if(l>r) return;
int mid = (l+r)/2;
setdpup(posl, min(mid,posr));
pair<ll, ll> bestans(getmxbet(D-2*mid+ST+posl), posl);
for(int i=posl+1; i<=min(mid, posr); i++) {
setdpup(i, min(mid, posr));
bestans = max(bestans, {getmxbet(D-2*mid+ST+i), i});
}
cbans = max(cbans, bestans.first);
Q.push({{l, mid-1}, {posl, bestans.second}});
Q.push({{mid+1, r}, {bestans.second, posr}});
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
cbans=0; N=n;
D=d; ST=start;
vector<pair<int, int>> idxval;
for(int i=0;i<n;i++) {
atar[i] = attraction[i];
idxval.emplace_back(attraction[i], i);
}
sort(idxval.begin(), idxval.end());
for(int i=0;i<n;i++) {pospos[idxval[i].second]=i;}
rundp1(0, start, 0, n-1);
while(!Q.empty()) {
auto e = Q.front(); Q.pop();
rundp1(e.first.first, e.first.second, e.second.first, e.second.second);
}
rundp2(start, n-1, 0, n-1);
while(!Q.empty()) {
auto e = Q.front(); Q.pop();
rundp2(e.first.first, e.first.second, e.second.first, e.second.second);
}
return cbans;
}
/*
int val[5] = {7, 5, 1, 10, 12};
int main() {
cout << findMaxAttraction(5, 2, 8, val);
//cout << qr(roots[2], roots[3], 5);
}*/
