//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "holiday.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
int *arr, N, st, D;
ll sumK(int k, int a, int b)
{
vi foo;
for(int i = a; i<= b; i++) foo.pb(arr[i]);
sort(foo.begin(), foo.end());
ll ret = 0;
while(!foo.empty() && k)
{
ret += foo.back();
foo.pop_back();
k--;
}
return ret;
}
ll solve(int L = 0, int R = st, int i = st, int j = N-1)
{
if(L> R) return 0;
int M = (L+R)/2;
int opt = i;
ll res = -4e18;
for(int p = i; p<= j; p++)
{
int a = st-M, b = p-st;
int del = min(a, b)*2+max(a, b);
if(del>= D) break;
ll here = sumK(D-del, M, p);
if(here> res)
{
res = here;
opt = p;
}
}
return max(max(solve(L, M-1, i, opt), solve(M+1, R, opt, j)), res);
}
long long findMaxAttraction(int n, int start, int d, int attraction[])
{
arr = attraction; N = n; st = start; D = d;
return solve();
return 0;
}
