#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int MAXN = 1e5 + 5;
int n, d, start, a[MAXN], root[MAXN];
long long ans = 0;
vector <int> cmp;
struct node_t {
int le, ri, cnt = 0;
long long sum = 0;
} it[18 * MAXN];
int Time;
void update(int pre, int nxt, int l, int r, int u, int val) {
if(l > u || r < u || l > r) return;
if(l == r) {
it[nxt].sum = it[pre].sum + 1LL * val * cmp[l - 1];
it[nxt].cnt = it[pre].cnt + val;
return;
}
int mid = l + r >> 1;
if(u <= mid) {
it[nxt].ri = it[pre].ri;
it[nxt].le = ++Time;
update(it[pre].le, it[nxt].le, l, mid, u, val);
} else {
it[nxt].le = it[pre].le;
it[nxt].ri = ++Time;
update(it[pre].ri, it[nxt].ri, mid + 1, r, u, val);
}
it[nxt].cnt = it[it[nxt].le].cnt + it[it[nxt].ri].cnt;
it[nxt].sum = it[it[nxt].le].sum + it[it[nxt].ri].sum;
}
long long getMax(int pre, int nxt, int l, int r, int cnt) {
if(cnt <= 0) return 0;
if(l == r) return 1LL * cnt * cmp[l - 1];
int mid = l + r >> 1;
int tmp = it[it[nxt].ri].cnt - it[it[pre].ri].cnt;
if(cnt <= tmp) return getMax(it[pre].ri, it[nxt].ri, mid + 1, r, cnt);
long long ans = it[it[nxt].ri].sum - it[it[pre].ri].sum;
ans += getMax(it[pre].le, it[nxt].le, l, mid, cnt - tmp);
return ans;
}
void divide_and_conquer(int l, int r, int u, int v) {
if(l > r) return;
int mid = l + r >> 1;
long long cost = -1;
int p = u;
for (int i = u; i <= v; ++i) {
int L = start - mid, R = i - start, cnt = d - L - R - min(L, R);
cnt = min(cnt, i - mid + 1);
if(cnt < 0) continue;
long long tmp = getMax(root[mid - 1], root[i], 1, n, cnt);
if(cost < tmp) {
cost = tmp;
p = i;
}
}
ans = max(ans, cost);
divide_and_conquer(l, mid - 1, u, p);
divide_and_conquer(mid + 1, r, p, v);
}
long long findMaxAttraction(int _n, int _start, int _d, int A[]) {
ans = Time = 0;
n = _n, d = _d, start = _start + 1;
for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
cmp = vector <int> (a + 1, a + n + 1);
sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin() + 1;
}
for (int i = 1; i <= n; ++i) {
root[i] = ++Time;
update(root[i - 1], root[i], 1, n, a[i], 1);
}
divide_and_conquer(1, start, start, n);
return ans;
}
// Dream it. Wish it. Do it.
