#include<bits/stdc++.h>
#include<holiday.h>
using namespace std;
#define int long long
struct segtree{
vector<pair<int,int> > tree;
segtree(int n){
tree.resize(n*4);
}
pair<int,int> merge(pair<int,int> a, pair<int,int> b){
return {a.first+b.first, a.second+b.second};
}
pair<int,int> update(int l, int r, int v, int x, int val, bool add){
if(x<l || r<=x) return tree[v];
if(l+1==r){
return tree[v]={add, val};
}
int m=l+(r-l)/2;
return tree[v]=merge(update(l, m, v*2+1, x, val, add), update(m, r, v*2+2, x, val, add));
}
pair<int,int> query(int l, int r, int v, int ql, int qr){
if(qr<=l || r<=ql) return {0, 0};
if(ql<=l && r<=qr) return tree[v];
int m=l+(r-l)/2;
return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
}
};
int bestk(int d, segtree seg, int n){
if(d<=0) return 0;
int l=0; int r=n;
int ans=0;
while(l<=r){
int m=l+(r-l)/2;
auto val=seg.query(0, n, 0, 0, m);
if(val.first<=d){
ans=val.second;
l=m+1;
}
else{
r=m-1;
}
}
return ans;
}
long long findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
vector<int> ind(n);
vector<pair<int,int> > sorted(n);
for(int i=0; i<n; i++){
sorted[i]={attraction[i], i};
}
sort(sorted.begin(), sorted.end());
reverse(sorted.begin(), sorted.end());
for(int i=0; i<n; i++){
ind[sorted[i].second]=i;
}
int ans=0;
segtree seg(n);
for(int l=start; l>=0; l--){
seg.update(0, n, 0, ind[l], attraction[l], true);
for(int r=start; r<n; r++){
if(r!=start){
seg.update(0, n, 0, ind[r], attraction[r], true);
}
int days=d-(r-l+min(r-start, start-l));
if(0<days){
ans=max(ans, bestk(days, seg, n));
}
}
for(int r=start+1; r<n; r++){
seg.update(0, n, 0, ind[r], 0, false);
}
}
return ans;
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int32_t n, start, d;
cin >> n >> start >> d;
int32_t a[n];
for(int i=0; i<n; i++){
cin >> a[i];
}
cout << findMaxAttraction(n, start, d, a) << "\n";
}*/
