#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define emb emplace_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e9
typedef tuple<int,int,int,int> iiii;
struct Node{
int64_t sum;
int sz,l,r;
Node(){sz=sum=l=r=0;}
Node(int ll,int rr){sz=sum=0;l=ll;r=rr;}
};
vector<Node> st;
vector<int> root;
vector<int> zort;
int addNode(int l,int r){
st.emplace_back(l,r);
st.back().sz=st[l].sz+st[r].sz;
st.back().sum=st[l].sum+st[r].sum;
return st.size()-1;
}
int update(int node,int l,int r,int qx){
if(l==r){
if(!node)
node=addNode(0,0);
st[node].sz++;
st[node].sum+=zort[qx];
return node;
}
int mid=(l+r)/2;
if(qx<=mid)
return addNode(update(st[node].l,l,mid,qx),st[node].r);
else
return addNode(st[node].l,update(st[node].r,mid+1,r,qx));
}
int64_t query(int nodeL,int nodeR,int l,int r,int qk){
if(l==r) return 1LL*qk*zort[l];
int t=st[st[nodeR].r].sz-st[st[nodeL].r].sz;
int mid=(l+r)/2;
if(qk>=t)
return query(st[nodeL].l,st[nodeR].l,l,mid,qk-t)+(st[st[nodeR].r].sum-st[st[nodeL].r].sum);
else
return query(st[nodeL].r,st[nodeR].r,mid+1,r,qk);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
for(int i=0;i<n;i++)
zort.pb(attraction[i]);
sort(all(zort));
zort.resize(unique(all(zort))-zort.begin());
root.pb(addNode(0,0));
for(int i=0;i<n;i++){
int j=lower_bound(all(zort),attraction[i])-zort.begin();
root.pb(update(root[i],0,zort.size()-1,j));
}
//~ cout << "yuppi" << endl;
int64_t ans=0;
queue<iiii> q;
q.emplace(0,start,start,n-1);
while(!q.empty()){
int optl,optr,l,r;
tie(optl,optr,l,r)=q.front();
q.pop();
//~ cout << optl sp optr sp l sp r << endl;
int mid=(l+r)/2;
pair<int64_t,int> opt={0,start};
for(int i=optl;i<=optr;i++){
int t=(mid-i)+min(start-i,mid-start);
if(t<=d){
int64_t val=query(root[i],root[mid+1],0,zort.size()-1,min(d-t,mid-i+1));
opt=max(opt,make_pair(val,i));
}
}
ans=max(ans,opt.first);
if(l<r){
q.emplace(optl,opt.second,l,mid-1);
q.emplace(opt.second,optr,mid+1,r);
}
}
return ans;
}
