#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e5 + 20;
ll dp[maxn];
int a[maxn] , d , root , lu[maxn] , ru[maxn] , l[maxn] , r[maxn];
vector<int> pnt , cmp;
void handle(int lux , int rux , int lx , int rx)
{
if(lx > rx)
return;
int k = (lx + rx) / 2;
l[k] = lx , r[k] = rx , lu[k] = lux , ru[k] = rux;
pnt.pb(k);
}
ll sum[maxn * 4];
int t[maxn * 4];
void add(int p , int val , int s = 0 , int e = cmp.size() , int v = 1)
{
if(e - s < 2)
{
t[v] += val;
sum[v] += cmp[s] * val;
return;
}
int m = (s + e) / 2;
if(p < m)
add(p , val , s , m , 2 * v);
else
add(p , val , m , e , 2 * v + 1);
t[v] = t[2 * v] + t[2 * v + 1];
sum[v] = sum[2 * v] + sum[2 * v + 1];
}
ll get(int k , int s = 0 , int e = cmp.size() , int v = 1)
{
if(k < 0)
return 0;
if(k >= t[v])
return sum[v];
if(e - s < 2)
return 1LL * k * cmp[s];
int m = (s + e) / 2;
return get(k , m , e , 2 * v + 1) + get(k - t[2 * v + 1] , s , m , 2 * v);
}
long long int findMaxAttraction(int n, int start, int D, int A[])
{
root = start;
d = D;
for(int i = 0; i < n; i++)
a[i] = A[i] , cmp.pb(a[i]);
sort(cmp.begin() , cmp.end());
cmp.resize(unique(cmp.begin() , cmp.end()) - cmp.begin());
for(int i = 0; i < n; i++)
a[i] = lower_bound(cmp.begin() , cmp.end() , a[i]) - cmp.begin();
int ans = 0;
handle(0 , root , root , n - 1);
for(;;)
{
if(pnt.empty())
break;
memset(t , 0 , sizeof t);
memset(sum , 0 , sizeof sum);
auto shit = pnt;
pnt.clear();
sort(shit.begin() , shit.end());
int ln = 0 , rn = -1;
for(auto p : shit)
{
while(rn < p)
{
rn++;
add(a[rn] , 1);
}
pair<ll , int> upd = {-1 , 0};
for(int i = lu[p]; i <= ru[p]; i++)
{
while(ln < i)
{
add(a[ln] , -1);
ln++;
}
int x = d - abs(i - root) - abs(p - root) - min(abs(i - root) , abs(p - root));
ll sum = get(x);
upd = max(upd , make_pair(sum , i));
}
dp[p] = upd.first;
handle(lu[p] , upd.second , l[p] , p - 1);
handle(upd.second , ru[p] , p + 1 , r[p]);
}
}
return *max_element(dp + root , dp + n);
}
