#include"holiday.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
multiset<int> not_used,used;
long long curr=0;
void pop_t()
{
not_used.insert(*used.begin());
curr-=(*used.begin());
used.erase(used.begin());
return;
}
void push_t()
{
used.insert(*prev(not_used.end()));
curr+=(*prev(not_used.end()));
not_used.erase(prev(not_used.end()));
return;
}
void dc(int dl,int dr,int attraction[],int s,int l,int r,vector<long long> &ans,int c)
{
if(dl>dr)
return;
// solving for mid
int dmid=(dl+dr)/2;
while(c*(l-s)+used.size()>dmid)
pop_t();
while(c*(l-s)+used.size()<dmid)
push_t();
int gg=l;
ans[dmid]=curr;
for(int i=l+1;i<r;i++)
{
for(int it=1;it<=c && !used.empty();it++)
pop_t();
if(!used.empty())
{
pop_t();
not_used.insert(attraction[i]);
push_t();
if(curr>ans[dmid])
{
ans[dmid]=curr;
gg=i;
}
}
else
not_used.insert(attraction[i]);
}
// cleaning and recursive calls
for(int i=r-1;i>l;i--)
{
if(not_used.find(attraction[i])!=not_used.end())
not_used.erase(not_used.find(attraction[i]));
else
{
curr-=attraction[i];
used.erase(used.find(attraction[i]));
}
}
dc(dl,dmid-1,attraction,s,l,gg+1,ans,c);
for(int i=l+1;i<=gg;i++)
not_used.insert(attraction[i]);
dc(dmid+1,dr,attraction,s,gg,r,ans,c);
for(int i=gg;i>l;i--)
{
if(not_used.find(attraction[i])!=not_used.end())
not_used.erase(not_used.find(attraction[i]));
else
{
curr-=attraction[i];
used.erase(used.find(attraction[i]));
}
}
return;
}
long long findMaxAttraction(int n,int start,int d,int attraction[])
{
vector<long long> ans[2][2];
for(int i:{0,1})
{
for(int j:{0,1})
{
ans[i][j].resize(d+10);
fill(ans[i][j].begin(),ans[i][j].end(),0);
}
}
for(int i=1;i<=d;i++)
not_used.insert(0);
for(int rev:{0,1})
{
not_used.insert(attraction[start]);
dc(0,d,attraction,start,start,n,ans[rev][0],1);
dc(0,d,attraction,start,start,n,ans[rev][1],2);
while(!used.empty())
pop_t();
not_used.erase(not_used.find(attraction[start]));
reverse(attraction,attraction+n);
start=n-1-start;
attraction[start]=0;
}
long long w=max(ans[0][0][d],ans[1][0][d]);
for(int i=0;i<=d;i++)
w=max({w,ans[0][1][i]+ans[1][0][d-i],ans[0][0][i]+ans[1][1][d-i]});
return w;
}
