#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
mt19937_64 bruh(chrono::steady_clock::now().time_since_epoch().count());
const int N = 150002;
const int M = 150002;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;
ll n, strt, d;
ll a[N];
ll szh[N];
ll L, R;
struct seg {
ll t[4 * N] = {0};
ll ts[4 * N] = {0};
void upd(ll p, ll c, ll z, ll v = 1, ll tl = 0, ll tr = n) {
if(tl == tr) {
t[v] += c;
ts[v] += z;
return;
}
ll m = (tl + tr) >> 1ll;
upd(p, c, z, v * 2, tl, m);
upd(p, c, z, v * 2 + 1, m + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
ts[v] = ts[v * 2] + ts[v * 2 + 1];
}
ll get(ll k, ll v = 1, ll tl = 0, ll tr = n) {
if(tl == tr) {
ll z = ts[v]/t[v];
return min(t[v], k) * z;
}
ll m = (tl + tr) >> 1ll;
if(k <= t[v * 2 + 1])return get(k, v * 2 + 1, m + 1, tr);
return get(k - t[v * 2 + 1], v * 2, tl, m) + ts[v * 2 + 1];
}
} rt;
void add(ll pos) {
rt.upd(szh[pos], 1, a[pos]);
}
void del(ll pos) {
rt.upd(szh[pos], -1, -a[pos]);
}
void sdvig(ll l, ll r) {
while(R < r) add(++R);
while(l < L) add(--L);
while(l > L) del(L++);
while(R > r) del(R--);
}
ll ans[N];
void solve(int l, int r, int optl, int optr) {
if(l > r)return;
int m = (l + r) >> 1ll;
int opt = strt;
ans[m] = -1e9;
for(int j = max(m, optl); j <= optr; j++) {
sdvig(m, j);
ll ost = d - ((strt - m) + (j - strt) + min(j - strt, strt - m));
if(ost < 0)continue;
if(ans[m] < rt.get(ost))
ans[m] = rt.get(ost), opt = j;
}
solve(l, m - 1, optl, opt);
solve(m + 1, r, opt, optr);
}
long long int findMaxAttraction(int n, int start, int D, int attraction[]) {
vector<int> szha;
for(int i = 1; i <= n; i++)
a[i] = attraction[i - 1], szha.pb(a[i]);
strt = start + 1, d = D;
sort(szha.begin(), szha.end());
szha.erase(unique(szha.begin(), szha.end()), szha.end());
for(int i = 1; i <= n; i++)
szh[i] = lower_bound(szha.begin(), szha.end(), a[i]) - szha.begin();
solve(1, strt, strt, n);
ll answw = 0;
for(int i = 1; i <= strt; i++)
answw = max(answw, ans[i]);
return answw;
}
