#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=3e5+5;
pair<int,ll> segtree[nax*4];
void build(int pos,int l,int r){
if(l==r){
segtree[pos]={0,0};
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos].fi=segtree[pos*2+1].fi+segtree[pos*2+2].fi;
segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
return;
}
void update(int pos,int l,int r,int idx,int value){
if(l==r){
segtree[pos].fi=value;
segtree[pos].se=( value > 0 ? 1 : 0);
return;
}
int mid=(r+l)/2;
if(mid>=idx) update(pos*2+1,l,mid,idx,value);
else update(pos*2+2,mid+1,r,idx,value);
segtree[pos].fi=segtree[pos*2+1].fi+segtree[pos*2+2].fi;
segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
//cout <<l<<" "<<r<<" "<<segtree[pos].fi<<endl;
return;
}
long long query(int pos,int l,int r,int cnt){
if(l==r) return (cnt>=segtree[pos].se ? segtree[pos].fi : 0);
int mid=(r+l)/2;
//cout <<cnt<<" "<<l<<" "<<r<<" "<<segtree[pos].fi<<endl;
if(cnt>=segtree[pos*2+2].se){
return query(pos*2+1,l,mid,cnt-segtree[pos*2+2].se)+segtree[pos*2+2].fi;
}else{
return query(pos*2+1,l,mid,cnt);
}
}
vector<int> a;
vector<int> b;
pair<ll,int> lefty[nax];
pair<ll,int> righty[nax];
vector<int> cnt(nax);
int m;
void daq(int l,int r,int optl,int optr,int idx){
int mid=(r+l)/2;
for (int i = optl; i <= optr; ++i)
{
update(0,0,m-1,cnt[i],(idx ? b[i] : a[i]));
ll cur=query(0,0,m-1,mid-i);
//cout <<" "<<mid<<" "<<cnt[i]<<" "<<segtree[0].se<<" "<<segtree[0].fi<<endl;
if((idx ? righty[mid].fi : lefty[mid].fi) < cur){
(idx ? righty[mid] : lefty[mid])={cur,i};
}
}
//cout <<mid<<" "<<optl<<" "<<optr<<" "<<righty[mid].fi<<" "<<righty[mid].se<<endl;
for (int i = optr; i >= optl; --i)
{
update(0,0,m-1,cnt[i],0);
}
if(l>=r) return;
if(l!=mid) daq(l,mid-1,optl,(idx ? righty[mid].se : lefty[mid].se),idx);
for (int i = optl; i <= (idx ? righty[mid].se : lefty[mid].se); ++i)
{
update(0,0,m-1,cnt[i],(idx ? b[i] : a[i]));
}
daq(mid+1,r,(idx ? righty[mid].se : lefty[mid].se),optr,idx);
for (int i = (idx ? righty[mid].se : lefty[mid].se); i <= optr; ++i)
{
update(0,0,m-1,cnt[i],(idx ? b[i] : a[i]));
}
return;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<pair<int,int>> tab;
for (int i = 0; i < start; ++i)
{
a.pb(attraction[i]);
}
for (int i = start; i < n; ++i)
{
b.pb(attraction[i]);
}
reverse(a.begin(),a.end());
for (int i = 0; i < a.size(); ++i)
{
tab.pb({a[i],i});
}
sort(tab.begin(),tab.end());
for (int i = 0; i < tab.size(); ++i)
{
cnt[tab[i].se]=i;
}
m=a.size();
if(a.size()){
build(0,0,m-1);
daq(0,d,0,m-1,0);
}
tab.clear();
for (int i = 0; i < b.size(); ++i)
{
tab.pb({b[i],i});
}
sort(tab.begin(),tab.end());
for (int i = 0; i < tab.size(); ++i)
{
cnt[tab[i].se]=i;
}
m=b.size();
if(b.size()){
build(0,0,m-1);
daq(0,d,0,m-1,1);
}
long long ans=0;
for (int i = 0; i <= d; ++i)
{
ans=max(ans,righty[i].fi+( d >= righty[i].se+i+1 ? lefty[d-righty[i].se-i-1].fi : 0));
if(i) ans=max(ans,lefty[i-1].fi+( d>= lefty[i-1].se+i+1 ? righty[d-lefty[i].se-i-1].fi : 0));
}
return ans;
}
