#include "holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =2e5+10;
const ll mod=1e9+7;
const ll base=1e15;
ll st[4*maxn];
ll st1[4*maxn];
ll val[maxn];
ll pos[maxn];
struct tk
{
ll n;
ll l=1;
ll r=0;
void update(ll id,ll left,ll right,ll x,ll diff)
{
if (x>right||x<left)
return ;
if (left==right)
{
st[id]+=diff;
st1[id]+=val[left]*diff;
return ;
}
ll mid=(left+right)/2;
update(id*2,left,mid, x, diff);
update(id*2+1,mid+1, right, x, diff);
st[id]=st[id*2]+st[id*2+1];
st1[id]=st1[id*2]+st1[id*2+1];
}
void finit(ll n1)
{
l=1;
r=0;
init(1,1,n1);
n=n1;
}
void init(ll id,ll left,ll right)
{
st[id]=0;
st1[id]=0;
if (left==right)
return ;
ll mid=(left+right)/2;
init(id*2,left,mid);
init(id*2+1,mid+1, right);
}
void ers(ll t)
{
update(1,1,n,t,-1);
}
void add(ll t)
{
update(1,1,n,t,1);
}
ll get1(ll lf,ll rt,ll x)
{
if (x<0) return -1e15;
while (l>lf)
{
l--;
add(pos[l]);
}
while (l<lf)
{
ers(pos[l]);
l++;
}
while (r<rt)
{
r++;
add(pos[r]);
}
while (r>rt)
{
ers(pos[r]);
r--;
}
if (x>st[1])
{
return st1[1];
}
return get(1,1,n,x);
}
ll get(ll id,ll left,ll right,ll x)
{
if (left==right)
{
return val[left]*x;
}
ll mid=(left+right)/2;
if (st[id*2+1]<x)
{
return get(id*2,left,mid,x-st[id*2+1])+st1[id*2+1];
}
else
{
return get(id*2+1,mid+1,right,x);
}
}
} man;
ll ans[maxn];
void dac(ll start,ll l,ll r,ll low,ll high,ll d)
{
if (l>r) return ;
ll mid=(l+r)/2;
ll pos_best=-1;
ans[mid]=-1e15;
for (int i=low;i<=high;i++)
{
ll kc=mid-start;
if (i!=start)
{
kc+=mid-i;
}
ll t=man.get1(i,mid,d-kc);
if (ans[mid]<t)
{
ans[mid]=t;
pos_best=i;
}
}
/*if (mid==5)
{
cout <<ans[mid]<<" "<<pos_best<<endl;
}*/
dac(start,l,mid-1,low,pos_best,d);
dac(start,mid+1,r,pos_best,high,d);
}
ll dosth(ll start,ll n,ll d)
{
man.finit(n);
// cout <<
dac(start,start,min(n,start+d),1,start,d);
ll res=0;
for (int i=1;i<=n;i++)
{
res=max(res,ans[i]);
}
return res;
}
ll findMaxAttraction(int n,int start,int d,int attraction[])
{
vector<ll> vt;
for (int i=0; i<n; i++)
{
pos[i+1]=attraction[i];
vt.pb(pos[i+1]);
}
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
ll siz=vt.size();
for (int i=1; i<=siz; i++)
{
val[i]=vt[i-1];
// cout <<val[i]<<" ";
}
// cout <<endl;
for (int i=1; i<=n; i++)
{
pos[i]=lower_bound(vt.begin(),vt.end(),pos[i])-vt.begin()+1;
// cout <<pos[i]<<" ";
}
// cout <<endl;
//cout <<siz<<endl;
man.finit(n);
start++;
ll ans=dosth(start, n,d);
// cout <<dosth(start,n,d)<<endl;
reverse(pos+1,pos+n+1);
ans=max(ans,dosth(n-start+1,n,d));
/* for (int i=1;i<=n;i++)
{
cout <<pos[i]<<" ";
}
cout <<endl;
cout <<start<<endl;
cout <<dosth(n-start+1,n,d)<<endl;*/
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
int t[100];
t[0]=10;
t[1]=2;
t[2]=20;
t[3]=30;
t[4]=1;
cout <<findMaxAttraction(5,2,7,t)<<endl;
}*/
