#include"holiday.h"
#include <vector>
#include <algorithm>
using namespace std;
int poz[100005];
int nodes=0;
//int root[10005];
//int fiust[3200005];
//int fiudr[3200005];
long long rez[300005][4];
int unmap[100005];
vector<pair<int,int> >v0,v1,v2,v3;
vector<pair<int,int> >event[30005];
int stanga[300005];
int idx[300005];
int stpos[300005];
int strr[3005][3005];
int noduri=0;
int overtook[300005];
int nmax,n,dmax;
int find(int a)
{
if(overtook[a]==a)
{
return a;
}
return overtook[a]=find(overtook[a]);
}
long long heighest(int index,int k)
{
long long suma=0;
for(int i=nmax;i>=0;i--)
{
if(strr[index][i]>=1 && k>=1)
{
suma=suma+unmap[i];
k--;
}
}
return suma;
}
long long value(int index,int timp)
{
if(timp<=stpos[index])
{
return 0;
}
return heighest(index,timp-stpos[index]);
}
void compare(int idx1,int idx2)
{
int st=0,dr=dmax;
while(st<=dr)
{
int mij=(st+dr)/2;
if(value(idx1,mij)<value(idx2,mij))
{
dr=mij-1;
}
else
{
st=mij+1;
}
}
if(dr+1<=dmax)
{
event[dr+1].push_back({1,idx2});
}
}
void add(int index,int startpos)
{
if(noduri==0)
{
noduri++;
stpos[noduri]=startpos;
stanga[noduri]=-1;
overtook[noduri]=noduri;
for(int i=0;i<=nmax;i++)
{
strr[noduri][i]=0;
}
strr[noduri][poz[index]]=1;
}
else
{
noduri++;
stpos[noduri]=startpos;
stanga[noduri]=noduri-1;
overtook[noduri]=noduri;
for(int i=0;i<=nmax;i++)
{
strr[noduri][i]=strr[noduri-1][i];
}
strr[noduri][poz[index]]=1;
compare(stanga[noduri],noduri);
}
}
void overtake(int index)
{
if(overtook[index]==index)
{
overtook[stanga[index]]=index;
stanga[index]=stanga[stanga[index]];
if(stanga[index]!=-1)
{
compare(stanga[index],index);
}
}
}
void calc(int tiprez,vector<pair<int,int> >vec)
{
noduri=0;
for(int i=0;i<vec.size();i++)
{
event[vec[i].first].push_back({0,vec[i].second});
}
for(int i=0;i<=dmax;i++)
{
while(event[i].size())
{
auto x=event[i].back();
event[i].pop_back();
if(x.first==0)
{
add(x.second,i);
}
else
{
overtake(x.second);
}
}
if(noduri>=1)
rez[i][tiprez]=value(find(1),i);
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
nmax=n;
dmax=d;
start++;
vector<pair<int,int> >vec;
for(int i=1; i<=n; i++)
{
vec.push_back({attraction[i-1],i});
}
sort(vec.begin(),vec.end());
for(int i=0;i<n;i++)
{
poz[vec[i].second]=i;
unmap[i]=vec[i].first;
}
for(int i=start;i<=n;i++)
{
v0.push_back({i-start,i});
v1.push_back({(i-start)*2,i});
}
for(int i=start-1;i>=1;i--)
{
v2.push_back({start-i,i});
v3.push_back({(start-i)*2,i});
}
calc(0,v0);
calc(1,v1);
calc(2,v2);
calc(3,v3);
long long sol=0;
for(int i=0;i<=dmax;i++)
{
sol=max(sol,rez[i][0]+rez[d-i][3]);
sol=max(sol,rez[i][1]+rez[d-i][2]);
}
return sol;
}
