#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
typedef long long ll;
typedef pair<int, ll> point;
const int MAXN = 1e5 + 5, off = 1 << 17, MAX = 3e5 + 5;
int S;
int a[MAXN], convert[MAXN];
point T[2 * off];
ll ans[MAX + 5][3][2];
#define qunatity first
#define sum second
point operator +(const point &A, const point &B) {
point ret;
ret.qunatity = A.qunatity + B.qunatity;
ret.sum = A.sum + B.sum;
return ret;
}
void shine(int i) {
i = convert[i];
i += off;
assert(T[i].qunatity == 0);
T[i].qunatity = 1;
T[i].sum = a[i - off];
for(i /= 2; i; i /= 2) {
T[i] = T[i * 2] + T[i * 2 + 1];
}
}
void fade(int i) {
i = convert[i];
i += off;
assert(T[i].qunatity == 1);
T[i].qunatity = 0;
T[i].sum = 0;
for(i /= 2; i; i /= 2) {
T[i] = T[i * 2] + T[i * 2 + 1];
}
}
ll query(int k, int x = 1) {
if(T[x].qunatity <= k) {
return T[x].sum;
}
if(x >= off) {
return 0;
}
if(T[x * 2 + 1].qunatity <= k) {
return query(k - T[x * 2 + 1].qunatity, x * 2) + T[x * 2 + 1].sum;
}
return query(k, x * 2 + 1);
}
void calc(int lo, int hi, int from, int to, int mul, int heading) {
if(lo > hi) return;
int mid = (lo + hi) >> 1;
int pivot = from; ll best = 0;
int d = from < to ? 1 : -1;
for(int i = from; i != to + d; i += d) {
shine(i);
ll value = query(mid - abs(S - i) * mul);
if(value > best) {
pivot = i;
best = value;
}
}
ans[mid][mul][heading] = best;
for(int i = pivot; i != to + d; i += d) {
fade(i);
}
calc(mid + 1, hi, pivot, to, mul, heading);
for(int i = from; i != pivot; i += d) {
fade(i);
}
calc(lo, mid - 1, from, pivot, mul, heading);
}
ll findMaxAttraction(int n, int s, int d, int attraction[]) {
memset(ans, 0, sizeof ans);
vector<point> v;
REP(i, n) {
a[i] = attraction[i];
v.push_back({a[i], i});
}
sort(v.begin(), v.end());
REP(i, n) {
convert[v[i].second] = i;
}
sort(a, a + n);
S = s;
if(s < n - 1) {
calc(2, MAX, s + 1, n - 1, 1, 1);
calc(3, MAX, s + 1, n - 1, 2, 1);
}
if(s) {
calc(2, MAX, s - 1, 0, 1, 0);
calc(3, MAX, s - 1, 0, 2, 0);
}
int addition = 0; ll sol = 0;
REP(k, 2) {
REP(dd, d + 1 - k) {
sol = max(sol, ans[dd][2][1] + ans[d - dd - k][1][0] + addition);
sol = max(sol, ans[dd][2][0] + ans[d - dd - k][1][1] + addition);
}
addition += a[convert[s]];
}
return sol;
}
