#include"holiday.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1<<18;
const int M=2e5+10;
const int K=3e5+10;
vector<pair<ll,int>> con;
ll arr[M];
int tst,fi[M];
pair<ll,int> f[K],g[K];
queue<tuple<int,int,int,int>> q;
struct node{
ll val;
int fre;
friend node operator+(const node &a,const node &b){
node ret;
ret.val=a.val+b.val;
ret.fre=a.fre+b.fre;
return ret;
}
}s[N];
void build(int l,int r,int idx){
s[idx]={0,0};
if(l==r) return;
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx]=s[idx*2]+s[idx*2+1];
}
void update(int l,int r,int idx,int a){
if(a<l || a>r) return;
if(l==r){
if(s[idx].fre==0){
s[idx].fre=1;
s[idx].val=con[l].first;
//cout<<"open" <<l <<" " <<s[idx].val <<"\n";
}
else{
s[idx].fre=0;
s[idx].val=0;
}
return;
}
int m=(l+r)/2;
update(l,m,idx*2,a);
update(m+1,r,idx*2+1,a);
s[idx]=s[idx*2]+s[idx*2+1];
}
ll query(int l,int r,int idx,int k){
if(k>=s[idx].fre) return s[idx].val;
if(l==r) return 0;
int m=(l+r)/2;
if(k>s[idx*2+1].fre) return query(l,m,idx*2,k-s[idx*2+1].fre)+s[idx*2+1].val;
return query(m+1,r,idx*2+1,k);
}
void pt(int l,int r,int idx,int a){
if(a<l || a>r) return;
if(l==r){
cout<<s[idx].val <<" ";
return;
}
int m=(l+r)/2;
pt(l,m,idx*2,a);
pt(m+1,r,idx*2+1,a);
}
ll run(int n,int start,int d){
build(0,n-1,1);
con.clear();
for(int i=0;i<n;i++) con.push_back({arr[i],i});
q.push({0,d,start,n-1});
sort(con.begin(),con.end());
for(int i=0;i<n;i++){
fi[con[i].second]=i;
}
// for(int i=0;i<n;i++) cout<<fi[i] <<" ";
// cout<<"\n";
int now=start-1;
while(!q.empty()){
auto [l,r,sl,sr]=q.front();
q.pop();
//cout<<"sv" <<l <<" " <<r <<" " <<sl <<" " <<sr <<"\n";
if(l>r) continue;
int mid=(l+r)/2;
//cout<<"fd" <<mid <<"\n";
pair<ll,int> mx={0,-1};
for(int i=sl;i<=sr;i++){
//cout<<"i" <<i <<"\n";
while(now<i){
now++;
update(0,n-1,1,fi[now]);
}
while(now>i){
update(0,n-1,1,fi[now]);
now--;
}
//cout<<"qr" <<s[1].val <<" " <<s[1].fre <<"\n";
// for(int i=0;i<n;i++) pt(0,n-1,1,i);
// cout<<"\n";
int lt=mid-abs(start-i);
if(lt<0) break;
ll cand=query(0,n-1,1,lt);
//cout<<"got" <<cand <<"\n";
if(mx.first<cand){
mx.first=cand;
mx.second=i;
}
}
f[mid]=mx;
q.push({l,mid-1,sl,f[mid].second});
q.push({mid+1,r,f[mid].second,sr});
}
// cout<<"endd";
// cout<<"ckk";
// for(int i=0;i<=d;i++){
// cout<<i <<" " <<f[i].first <<" " <<f[i].second <<"\n";
// }
if(start==0){
return f[d].first;
}
ll ans=f[d].first;
// for(int i=0;i<n;i++) pt(0,n-1,1,i);
// cout<<"\n";
while(now>=start){
update(0,n-1,1,fi[now]);
now--;
}
// for(int i=0;i<n;i++) pt(0,n-1,1,i);
// cout<<"\n";
now=start;
q.push({0,d,0,start-1});
while(!q.empty()){
auto [l,r,sl,sr]=q.front();
q.pop();
// cout<<"sv" <<l <<" " <<r <<" " <<sl <<" " <<sr <<"\n";
if(l>r) continue;
int mid=(l+r)/2;
// cout<<"fd" <<mid <<"\n";
pair<ll,int> mx={0,-1};
for(int i=sr;i>=sl;i--){
// cout<<"i" <<i <<"\n";
while(now>i){
now--;
update(0,n-1,1,fi[now]);
}
while(now<i){
update(0,n-1,1,fi[now]);
now++;
}
int lt=mid-abs((start-1)-i);
// for(int i=0;i<n;i++) pt(0,n-1,1,i);
// cout<<"\n";
if(lt<0) break;
ll cand=query(0,n-1,1,lt);
// cout<<"got " <<cand <<"\n";
if(mx.first<cand){
mx.first=cand;
mx.second=i;
}
}
g[mid]=mx;
q.push({l,mid-1,g[mid].second,sr});
q.push({mid+1,r,sl,g[mid].second});
}
// cout<<"endd";
// for(int i=0;i<=d;i++){
// cout<<i <<" " <<g[i].first <<" " <<g[i].second <<"\n";
// }
while(now<start){
update(0,n-1,1,fi[now]);
now++;
}
// for(int i=0;i<n;i++) pt(0,n-1,1,i);
// cout<<"\n";
for(int i=1;i<d;i++){
//spend i with left side
int now=g[i].second;
ll cand=g[i].first;
int lt=d-1-i;
lt-=abs(start-now);
if(lt<0) break;
ans=max(ans,cand+f[lt].first);
}
return ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
tst=start;
build(0,n-1,1);
for(int i=0;i<n;i++) arr[i]=attraction[i];
ll ans=run(n,start,d);
reverse(arr,arr+n);
ans=max(ans,run(n,n-1-start,d));
return ans;
}
