//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
set <pii> ss1,ss2;
vector <int> val;
ll ans = 0,curans = 0;
int curl,curr;
int p,w;
void add(int pos) {
int tmp = val[pos];
if (!ss1.empty() and tmp>(*(--ss1.end())).fi) ss1.insert({tmp,pos}),curans += tmp;
else ss2.insert({tmp,pos});
}
void bye(int pos) {
int tmp = val[pos];
if (ss1.find(MP(tmp,pos))!=ss1.end()) curans -= tmp, ss1.erase(MP(tmp,pos));
else ss2.erase(MP(tmp,pos));
}
void modify(int sz) {
assert(sz>=0);
while (SZ(ss1)<sz and !ss2.empty()) {
auto tmp = (*(--ss2.end()));
ss2.erase(--ss2.end());
ss1.insert(tmp);
curans += tmp.fi;
}
while (SZ(ss1)>sz) {
auto tmp = (*ss1.begin());
ss1.erase(ss1.begin());
ss2.insert(tmp);
curans -= tmp.fi;
}
}
void dnc(int lmin,int lmax,int rl,int rr,int cop,int col,int cor) {
if (lmin>lmax) return;
int cur = lmin+lmax>>1;
while (curl>cur) add(--curl);
while (curl<cur) bye(curl++);
while (curr>rr) bye(curr--);
while (curr<rl) add(++curr);
if (curr!=rl and curr!=rr) while (curr>rl) bye(curr--);
int opt = -1;
ll optval = -1;
int sz = w-(cop*p+col*cur+cor*curr);
if (curr==rl) {
while (1) {
if (sz>=0) {
modify(sz);
if (curans > optval) optval = curans,opt = curr;
}
if (curr!=rr) add(++curr);
else break;
sz-=cor;
}
}
else {
assert(curr==rr);
while (1) {
if (sz>=0) {
modify(sz);
if (curans > optval) optval = curans,opt = curr;
}
if (curr!=rl) bye(curr--);
else break;
sz+=cor;
}
}
assert(opt!=-1);
// cout<<lmin<<" "<<lmax<<" "<<rl<<" "<<rr<<" "<<opt<<" "<<optval<<endl;
ans = max(ans,optval);
if (curr==rl) dnc(lmin,cur-1,rl,opt,cop,col,cor),dnc(cur+1,lmax,opt,rr,cop,col,cor);
else dnc(cur+1,lmax,opt,rr,cop,col,cor),dnc(lmin,cur-1,rl,opt,cop,col,cor);
}
ll findMaxAttraction(int n,int start,int d,int* attraction) {
if (d==0) return 0;
rep(i,0,n) val.pb(attraction[i]);
p = start,w=d;
curl = curr = p;
curans = val[p];
ss1.insert({val[p],p});
dnc(max(0,p-d/2),p,p,n-1,1,-2,1);
curl = curr = p;
curans = val[p];
while (!ss2.empty()) ss2.erase(ss2.begin());
while (!ss1.empty()) ss1.erase(ss1.begin());
ss1.insert({val[p],p});
dnc(max(0,p-d),p,p,n-1,-1,-1,2);
return ans;
}
