#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n,d;
int start;
int a[100010];
map<int,int> mp;
auto it=mp.begin();
ll tot_max=0,k=0;
ll res;
int st,ed,pos,p2;
void movel(int x,int dl)
{
while(st>x)
{
st--;
mp[a[st]]++;
k-=dl;
if(a[st]>(it->first))
{
pos++;
tot_max+=a[st];
}
while(k<pos)
{
pos--;
tot_max-=(it->first);
p2--;
if(!p2)
{
it++;
p2=(it->second);
}
}
while(k>pos)
{
if(it==mp.begin() && (it->second)==p2) break;
pos++;
p2++;
if(p2>(it->second))
{
it--;
p2=1;
}
tot_max+=(it->first);
}
}
while(st<x)
{
k+=dl;
if(a[st]>(it->first) || (a[st]==(it->first) && p2==(it->second)))
{
pos--;
tot_max-=a[st];
if(a[st]==(it->first))
{
p2--;
if(!p2)
{
if(it==mp.begin())
{
it++;
p2=(it->second);
}
else
{
it--;
pos++;
p2=1;
tot_max+=(it->first);
}
}
}
}
mp[a[st]]--;
if(!mp[a[st]]) mp.erase(a[st]);
while(k<pos)
{
pos--;
tot_max-=(it->first);
p2--;
if(!p2)
{
it++;
p2=(it->second);
}
}
while(k>pos)
{
if(it==mp.begin() && (it->second)==p2) break;
pos++;
p2++;
if(p2>(it->second))
{
it--;
p2=1;
}
tot_max+=(it->first);
}
st++;
}
}
void mover(int y,int dr)
{
while(ed<y)
{
ed++;
k-=dr;
mp[a[ed]]++;
if(a[ed]>(it->first))
{
pos++;
tot_max+=a[ed];
}
while(k<pos)
{
pos--;
tot_max-=(it->first);
p2--;
if(!p2)
{
it++;
p2=(it->second);
}
}
while(k>pos)
{
if(it==mp.begin() && (it->second)==p2) break;
pos++;
p2++;
if(p2>(it->second))
{
it--;
p2=1;
}
tot_max+=(it->first);
}
}
while(ed>y)
{
k+=dr;
if(a[ed]>(it->first) || (a[ed]==(it->first) && p2==(it->second)))
{
pos--;
tot_max-=a[ed];
if(a[ed]==(it->first))
{
p2--;
if(!p2)
{
if(it==mp.begin())
{
it++;
p2=(it->second);
}
else
{
it--;
pos++;
p2=1;
tot_max+=(it->first);
}
}
}
}
mp[a[ed]]--;
if(!mp[a[ed]]) mp.erase(a[ed]);
while(k<pos)
{
pos--;
tot_max-=(it->first);
p2--;
if(!p2)
{
it++;
p2=(it->second);
}
}
while(k>pos)
{
if(it==mp.begin() && (it->second)==p2) break;
pos++;
p2++;
if(p2>(it->second))
{
it--;
p2=1;
}
tot_max+=(it->first);
}
ed--;
}
}
int test(int s,int l,int r,int dl,int dr)
{
if(l>r) return -1;
if(dl*(start-s)+dr*(l-start)>d) return -1;
int ans=l;
ll temp_res;
mover(l,dr);
movel(s,dl);
temp_res=tot_max;
for(int i=l+1;i<=r;i++)
{
if(dl*(start-s)+dr*(i-start)>d) break;
mover(i,dr);
if(tot_max>temp_res)
{
temp_res=tot_max;
ans=i;
}
}
res=max(res,temp_res);
return ans;
}
void alltest(int l1,int r1,int l2,int r2,int dl,int dr)
{
if(l1>r1 || l2>r2) return;
int temp;
if(l1==r1)
{
temp=test(l1,l2,r2,dl,dr);
return;
}
int mid=(l1+r1)>>1;
temp=test(mid,l2,r2,dl,dr);
alltest(l1,mid-1,l2,temp,dl,dr);
alltest(mid+1,r1,temp,r2,dl,dr);
}
long long int findMaxAttraction(int N, int sta, int D, int attraction[]) {
if(!D) return 0ll;
if(D==1) return (ll)attraction[sta];
n=N;
d=D;
start=sta;
for(int i=0;i<n;i++) a[i]=attraction[i];
st=sta;
ed=sta;
k=d;
tot_max=res=(ll)a[sta];
mp[a[st]]=1;
pos=1;
p2=1;
it=mp.begin();
alltest(max(0,sta-d),sta,sta,n-1,1,2);
st=sta;
ed=sta;
k=d;
tot_max=(ll)a[sta];
auto it3=mp.begin();
for(auto it2=mp.begin();it2!=mp.end();)
{
it3=it2;
it2++;
mp.erase(it3);
}
mp[a[st]]=1;
pos=1;
p2=1;
it=mp.begin();
alltest(max(0,sta-d/2),sta,sta,n-1,2,1);
return res;
}
