#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
typedef long long int ll;
ll t[4*MAXN];
int cnt[4*MAXN],idx[MAXN],N;
void upd(int v,int pos,int l,int r,int val,int c){
if(l==r){
t[v] = val;
cnt[v] = c;
return;
}
int tm = (l+r)/2;
if(pos<=tm)upd(2*v,pos,l,tm,val,c);
else upd(2*v+1,pos,tm+1,r,val,c);
t[v] = t[2*v] + t[2*v+1];
cnt[v] = cnt[2*v] + cnt[2*v+1];
}
void clr(int v,int l,int r){
t[v] = cnt[v] = 0;
if(l==r)return;
int tm = (l+r)/2;
clr(2*v,l,tm);
clr(2*v+1,tm+1,r);
}
ll query(int v,int l,int r,int k){
if(cnt[v] == k || l==r)return t[v];
int tm = (l+r)/2;
if(cnt[2*v+1] >= k)return query(2*v+1,tm+1,r,k);
else return t[2*v+1] + query(2*v,l,tm,k-cnt[2*v+1]);
}
void add(int i,int val,int c){upd(1,idx[i]+1,1,N,val,c);}
ll rwalk[2][3*MAXN]; //walk right turn back
ll lwalk[2][3*MAXN]; //walk left turn back
int f[MAXN]; //optimal endpoint
long long int findMaxAttraction(int n, int start, int d, int a[]) {
N = n;
ll ans = 0;
vector<pair<int,int>>b;
for(int i=0;i<n;i++)b.push_back({a[i],i});
sort(b.begin(),b.end());
for(int i=0;i<n;i++)idx[b[i].second] = i;
vector<array<int,4>>v;
v.push_back({start,n-1,0,d});
while(!v.empty()){
vector<array<int,4>>u;
for(auto x:v){
int l = x[0],r = x[1],L=x[2],R=x[3];
int k = (L+R)/2;
ll best = 0;
f[k] = l;
for(int i=l;i<=r;i++){
if(k-2*i <= 0)break;
add(i,a[i],1);
ll res = query(1,1,n,k-2*i);
if(res > best){
best = res;
f[k] = i;
}
}
rwalk[1][k] = best;
if(L!=R){
int mid = (L+R)/2;
if(mid-1 >= L)u.push_back({l,f[k],L,mid-1});
if(mid+1 <= R)u.push_back({f[k],r,mid+1,R});
}
}
clr(1,1,n);
v = u;
}
v.push_back({start,n-1,0,d});
while(!v.empty()){
vector<array<int,4>>u;
int cur = 0;
for(auto x:v){
int l = x[0],r = x[1],L=x[2],R=x[3];
int k = (L+R)/2;
ll best = 0;
f[k] = l;
for(int i=l;i<=r;i++){
if(k-i <= 0)break;
while(cur<=i){
add(cur,a[cur],1);
cur++;
}
ll res = query(1,1,n,k-i);
if(res > best){
best = res;
f[k] = i;
}
}
//cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<k<<" "<<best<<'\n';
lwalk[1][k] = best;
if(L!=R){
int mid = (L+R)/2;
if(mid-1 >= L)u.push_back({l,f[k],L,mid-1});
if(mid+1 <= R)u.push_back({f[k],r,mid+1,R});
}
}
clr(1,1,n);
v = u;
}
if(start == 0)return lwalk[1][d];
for(int i=0;i<=d;i++)ans = max(ans,rwalk[0][i] + rwalk[0][d-i]);
for(int i=0;i<=d;i++)ans = max(ans,lwalk[0][i] + lwalk[0][d-i]);
return ans;
}
