#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+5e4+6;
const ll INF=2e9;
ll att[MAXN];
ll low[MAXN],high[MAXN],n1,start1,d1;
priority_queue<ll> pq;
ll cur_sum;
ll fr[MAXN],ansr[MAXN];
ll fl[MAXN],ansl[MAXN];
//start1 will be in left
ll what_to_check[MAXN];
struct node
{
ll cnt_cities;
ll sum;
};
struct segment_tree
{
node tree[4*MAXN];
void init()
{
for(ll j=0;j<4*MAXN;j++)
{
tree[j].cnt_cities=0;
tree[j].sum=0;
}
}
void update(ll l,ll r,ll idx,ll pos,ll val)
{
if(l>pos)return;
if(r<pos)return;
if(l==r)
{
tree[idx].cnt_cities=1;
tree[idx].sum=val;
return;
}
ll mid=(l+r)/2;
update(l,mid,idx*2,pos,val);
update(mid+1,r,idx*2+1,pos,val);
tree[idx].cnt_cities=tree[idx*2].cnt_cities+tree[idx*2+1].cnt_cities;
tree[idx].sum=tree[idx*2].sum+tree[idx*2+1].sum;
}
ll query(ll l,ll r,ll idx,ll cnt_needed)
{
if(cnt_needed<0)return -INF;
if(cnt_needed==0)return 0;
if(cnt_needed>=tree[idx].cnt_cities)return tree[idx].sum;
//cout<<l<<" "<<r<<" "<<tree[idx].cnt_cities<<" "<<cnt_needed<<endl;
ll mid=(l+r)/2;
if(tree[idx*2+1].cnt_cities>=cnt_needed)return query(mid+1,r,idx*2+1,cnt_needed);
else return tree[idx*2+1].sum+query(l,mid,idx*2,cnt_needed-tree[idx*2+1].cnt_cities);
}
}tr;
ll num[MAXN];
void compute_right(ll factor)
{
ll max_time=(n1-start1)*factor+(n1-start1);
vector<pair<ll,ll> >llervals;
vector<pair<ll,ll> >new_llervals;
llervals.push_back({0,max_time});
for(;llervals.size()>0;)
{
memset(what_to_check,-1,sizeof(what_to_check));
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
if(xd.first-1>=0)low[mid]=ansr[xd.first-1];
else low[mid]=start1;
if(xd.second+1<=max_time)high[mid]=ansr[xd.second+1];
else high[mid]=n1;
for(ll j=low[mid];j<=high[mid];j++)
{
what_to_check[j]=mid;
}
}
tr.init();
for(ll i=start1;i<=n1;i++)
{
if(i!=start1)tr.update(1,n1,1,num[i],att[i]);
ll time1=what_to_check[i];
if(time1==-1)continue;
ll gg=tr.query(1,n1,1,time1-(i-start1)*factor);
if(gg>fr[time1])
{
fr[time1]=gg;
ansr[time1]=i;
}
}
new_llervals.clear();
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
if(xd.first==xd.second)continue;
if(xd.first<=mid-1)new_llervals.push_back({xd.first,mid-1});
if(mid+1<=xd.second)new_llervals.push_back({mid+1,xd.second});
}
llervals=new_llervals;
}
}
void compute_left(ll factor)
{
ll max_time=(start1-1)*factor+start1;
vector<pair<ll,ll> >llervals;
vector<pair<ll,ll> >new_llervals;
llervals.push_back({0,max_time});
for(;llervals.size()>0;)
{
memset(what_to_check,-1,sizeof(what_to_check));
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
if(xd.first-1>=0)low[mid]=ansl[xd.second+1];
else low[mid]=1;
if(xd.second+1<=max_time)high[mid]=ansl[xd.first-1];
else high[mid]=start1;
for(ll j=low[mid];j<=high[mid];j++)
{
what_to_check[j]=mid;
}
}
tr.init();
for(ll i=start1;i>=1;i--)
{
tr.update(1,n1,1,num[i],att[i]);
ll time1=what_to_check[i];
if(time1==-1)continue;
//cout<<"%% "<<i<<" "<<time1<<endl;
//cout<<time1-(start1-i)*factor<<endl;
ll gg=tr.query(1,n1,1,time1-(start1-i)*factor);
if(gg>fl[time1])
{
fl[time1]=gg;
ansl[time1]=i;
}
}
new_llervals.clear();
for(auto xd:llervals)
{
ll mid=(xd.first+xd.second)/2;
//cout<<"^^ "<<mid<<" "<<fl[mid]<<" "<<ansl[mid]<<endl;
if(xd.first==xd.second)continue;
if(xd.first<=mid-1)new_llervals.push_back({xd.first,mid-1});
if(mid+1<=xd.second)new_llervals.push_back({mid+1,xd.second});
}
llervals=new_llervals;
}
}
ll solve_right()
{
memset(fl,-1,sizeof(fl));
memset(fr,-1,sizeof(fr));
compute_right(2);
compute_left(1);
ll ret=0;
for(ll t1=0;t1<MAXN;t1++)
{
if(fl[t1]<0)continue;
if(fr[d1-t1]<0)continue;
ret=max(ret,fl[t1]+fr[d1-t1]);
//cout<<t1<<" "<<fl[t1]<<" "<<fr[d1-t1]<<endl;
}
return ret;
}
ll solve_left()
{
memset(fl,-1,sizeof(fl));
memset(fr,-1,sizeof(fr));
compute_right(1);
compute_left(2);
ll ret=0;
for(ll t1=0;t1<MAXN;t1++)
{
if(fr[t1]<0)continue;
if(fl[d1-t1]<0)continue;
ret=max(ret,fr[t1]+fl[d1-t1]);
}
return ret;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<pair<ll,ll> >by_value;
for(ll i=0;i<n;i++)
{
att[i+1]=attraction[i];
by_value.push_back({att[i+1],i+1});
}
sort(by_value.begin(),by_value.end());
for(ll i=0;i<by_value.size();i++)
{
num[by_value[i].second]=i+1;
}
n1=n;start1=start;d1=d;
start1++;
return max(solve_left(), solve_right());
}
