#include "holiday.h"
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int SZ=1<<17;
vector<pair<int,int>> V;
int N, s, d, A[100000], P[100000];
long long ans, SS[100000];
pair<long long,int> tree[2*SZ];
void add_tree(int n, int v1, int v2)
{
tree[n+=SZ].first+=v1;
tree[n].second+=v2;
while(n>>=1) {
tree[n].first=tree[2*n].first+tree[2*n+1].first;
tree[n].second=tree[2*n].second+tree[2*n+1].second;
}
}
int kth(int k)
{
int bit=1, s=0, e=SZ-1;
while(s<e) {
int m=(s+e)>>1;
if(tree[2*bit].second>=k) {
bit=2*bit;
e=m;
}
else {
k-=tree[2*bit].second;
bit=2*bit+1;
s=m+1;
}
}
return s;
}
long long get_sum(int s, int e)
{
long long ret=0;
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) ret+=tree[s++].first;
if(~e&1) ret+=tree[e--].first;
}
return ret;
}
void solve()
{
int cd=d-1, l=s, r, k;
long long sum=V[A[s]].first, t1, t2;
fill(tree,tree+2*SZ,make_pair(0,0));
add_tree(A[s],V[A[s]].first,1);
ans=max(ans,sum); P[s]=s;
SS[s]=V[A[s]].first;
for(int i=s-1;i>=0;i--) SS[i]=SS[i+1]+V[A[i]].first;
for(int i=s+1;i<N && i-s<d;i++) {
if(cd>i-l) {
cd-=i-l+1;
P[i]=l;
l=i;
ans=max(ans,sum+=V[A[i]].first);
add_tree(A[i],V[A[i]].first,1);
continue;
}
k=kth(i-l+1-cd);
if((t1=get_sum(0,k))<V[A[i]].first) {
cd=0;
P[i]=l;
l=i;
ans=max(ans,sum+=V[A[i]].first-t1);
for(;;) {
t1=kth(1);
add_tree(t1,-V[A[t1]].first,-1);
if(k==t1) break;
}
add_tree(A[i],V[A[i]].first,1);
}
}
r=l; l=s;
for(int i=s-1;i>=0 && 2*(s-i)<d;i--) {
if(cd>2*(l-i)) {
cd-=2*(l-i)+1;
l=i;
ans=max(ans,sum+=V[A[i]].first);
add_tree(A[i],V[A[i]].first,1);
continue;
}
k=kth(2*(l-i)+1-cd); t1=V[A[i]].first-get_sum(0,k);
if(3*(l-i)<=cd+r-P[r]+1) t2=SS[i]-SS[l]-V[A[r]].first;
else t2=-1;
if(max(t1,t2)>0) {
if(t1>t2) {
cd=0;
l=i;
ans=max(ans,sum+=t1);
for(;;) {
t1=kth(1);
add_tree(t1,-V[A[t1]].first,-1);
if(k==t1) break;
}
add_tree(A[i],V[A[i]].first,1);
while(r>s && tree[SZ+A[r]].second==0) {
cd+=r-P[r]+1;
r=P[r];
}
}
else {
cd-=3*(l-i)-(r-P[r]+1);
ans=max(ans,sum+=t2);
while(i<l--) add_tree(l,V[A[l]].first,1);
l=i;
add_tree(r,-V[A[r]].first,-1);
r=P[r];
}
}
}
}
long long findMaxAttraction(int n, int start, int d, int attraction[])
{
N=n; s=start; ::d=d;
if(d==0) return 0;
V.resize(N);
for(int i=0;i<N;i++) V[i]={attraction[i],i};
sort(V.begin(),V.end());
for(int i=0;i<N;i++) A[V[i].second]=i;
solve();
reverse(A,A+N); s=N-1-s;
solve();
return ans;
}
