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