//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;
const int maxn = 1e5+5;
int rev[maxn];
int rnk[maxn];
struct node
{
vi foo; vector< ll > qs;
node *left, *right;
node()
{
left = right = NULL;
}
int getNum(int x)
{
return ( (int) foo.size())-(lower_bound(foo.begin(), foo.end(), x)-foo.begin());
}
ll getSum(int x)
{
int k = lower_bound(foo.begin(), foo.end(), x)-foo.begin();
return qs.back() - (k?qs[k-1]:0);
}
int askNum(int i, int j, int x, int L = 0, int R = N-1)
{
if(i> R || j< L) return 0LL;
if(i<= L && R<= j)
{
return getNum(x);
}
int M = (L+R)/2;
int a = left->askNum(i, j, x, L, M);
int b = right->askNum(i, j, x, M+1, R);
return a+b;
}
ll askSum(int i, int j, int x, int L = 0, int R = N-1)
{
if(i> R || j< L) return 0LL;
if(i<= L && R<= j)
{
//printf("arrived %lld (%d) (%d, %d)\n", qs.back(), qs.size(), L, R);
return getSum(x);
}
//printf("kuy%d %d %d %d\n", i, j, L, R);
int M = (L+R)/2;
ll a = left->askSum(i, j, x, L, M);
ll b = right->askSum(i, j, x, M+1, R);
return a+b;
}
};
void merge(vi &A, vi &B, vi &C)
{
int x = 0, y = 0;
int n = B.size(), m = C.size();
while(x< n && y< m)
{
if(B[x]< C[y]) A.pb(B[x++]);
else A.pb(C[y++]);
}
while(x< n) A.pb(B[x++]);
while(y< m) A.pb(C[y++]);
}
node *build(int L, int R)
{
if(L == R)
{
node *ret = new node;
ret->foo.pb(rev[L]);
ret->qs.pb(arr[L]);
return ret;
}
int M = (L+R)/2;
node* ret = new node;
ret->left = build(L, M);
ret->right = build(M+1, R);
merge(ret->foo, ret->left->foo, ret->right->foo);
for(int i = 0; i< (int) ret->foo.size(); i++)
{
ret->qs.pb((ret->qs.empty()?0LL:ret->qs.back())+rnk[ret->foo[i]]);
}
//printf("%d to %d:\n", L, R);
//for(int i = 0; i< (int) ret->foo.size(); i++) printf("%lld ", ret->qs[i]);
//printf("(%d)\n", ret->qs.back());
//printf("\n");
return ret;
}
node *root;
ll sumK(int k, int a, int b)
{
int tot = b-a+1;
if(k>= tot) return root->askSum(a, b, -1);
int lo = 0, hi = N-1;
while(lo< hi)
{
int mid = (lo+hi)/2;
//printf("askNum(%d, %d, %d) = %d\n", a, b, mid, root->askNum(a, b, mid));
if(root->askNum(a, b, mid)<= k) hi = mid;
else lo = mid+1;
}
//printf("lo is %d\n", lo);
return root->askSum(a, b, lo);
}
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);
//printf("sumK(%d %d %d) = %lld\n", D-del, M, p, here);
if(here> res)
{
res = here;
opt = p;
}
}
//printf("%d\n", M);
return max(max(res != -4e18?solve(L, M-1, i, opt):0, 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;
vii foo;
for(int i = 0; i< n; i++) foo.pb(ii(arr[i], i));
sort(foo.begin(), foo.end());
for(int i = 0; i< n; i++)
{
rev[foo[i].Y] = i;
rnk[i] = foo[i].X;
}
root = build(0, n-1);
//printf("it's %d\n", sumK(3, 1, 4));
return solve();
}
