#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 3;
ll ans = 0,arr[N];
int id,D;
void go(int l1,int r1,int l2,int r2){
if (l1 > id) return;
if (l1 > r1) return;
int mid = (l1 + r1)/2,opt = 0;
ll mx = -1;
// cout<<"! "<<l1<<" "<<r1<<" -> "<<l2<<" "<<r2<<endl;
for (int i = l2; i <= r2; i++){
ll cur = 0;
int l = mid,r = i;
l = min(l,id);
r = max(r,id);
int len = r - l + min(r - id,id - l);
int cnt = D - len;
// cout<<"i = "<<i<<" -> "<<cnt<<endl;
multiset <int> st;
for (int j = l; j <= r; j++)
st.insert(arr[j]);
while (cnt > 0 && st.size() > 0){
--cnt;
cur += *(--st.end());
st.erase(--st.end());
}
// cout<<"cur = "<<cur<<endl;
if (cur > mx){
mx = cur;
opt = i;
}
}
// cout<<"optimal "<<mid<<" "<<opt<<" "<<mx<<endl;
ans=max(ans,mx);
if (l1 == r1) return;
go(l1,mid,l2,opt);
go(mid+1,r1,opt + 1,r2);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
D = d;
for (int i=0;i<n;i++)
arr[i]=attraction[i];
id = start;
go(0,n - 1,0,n - 1);
return ans;
}
