#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int N = 1e5 + 10;
const int M = 3e5 + 10;
const int inf = 1e9;
const int mod = 1e9 + 7;
int n, start, d, a[N], order[N];
// segment tree
long long st[4 * N];
int st_cnt[4 * N];
void update(int id, int l, int r, int p, int cnt, long long val) {
st_cnt[id] += cnt;
st[id] += val;
if (l == r) return;
int mid = (l + r) / 2;
if (p <= mid) update(id * 2, l, mid, p, cnt, val);
else update(id * 2 + 1, mid + 1, r, p, cnt, val);
}
void add(int i) {
update(1, 1, n, order[i], 1, a[i]);
}
void del(int i) {
update(1, 1, n, order[i], - 1, - a[i]);
}
long long get(int id, int k) {
if (k <= 0) return 0;
if (st_cnt[id] <= k) return st[id];
return get(id * 2 + 1, k) + get(id * 2, k - st_cnt[id * 2 + 1]) ;
}
bool cmp(int i, int j) {
return a[i] < a[j];
}
int dis(int l, int r) {
if (l > r) return 0;
if (start <= l) return r - start;
if (r <= start) return start - l;
return r - l + min(start - l, r - start);
}
int cur_l = 1, cur_r = 0;
long long sum(int l, int r, int k) {
if (r < cur_l || cur_r < l) {
for (int i = cur_l; i <= cur_r; i ++) del(i);
for (int i = l; i <= r; i ++) add(i);
} else {
if (cur_l <= l) {
for (int i = cur_l; i < l; i ++) del(i);
} else {
for (int i = l; i < cur_l; i ++) add(i);
}
if (r <= cur_r) {
for (int i = r + 1; i <= cur_r; i ++) del(i);
} else {
for (int i = cur_r + 1; i <= r; i ++) add(i);
}
}
cur_l = l;
cur_r = r;
return get(1, k);
}
long long ans = 0;
void dvc(int l, int r, int x, int y) {
if (l > r) return;
int m = (l + r) / 2;
long long best_sum = 0;
int best = - 1;
for (int i = x; i <= y; i ++) {
long long cur = sum(m, i, d - dis(m, i));
if (cur > best_sum) {
best_sum = cur;
best = i;
}
}
//cout << m << " : " << best << " " << best_sum << "\n";
ans = max(ans, best_sum);
dvc(l, m - 1, x, best);
dvc(m + 1, r, best, y);
}
long long int findMaxAttraction(int _n, int _start, int _d, int *attraction) {
n = _n;
start = _start + 1;
d = _d;
int pos[n + 1];
for (int i = 1; i <= n; i ++) {
a[i] = attraction[i - 1];
pos[i] = i;
}
sort(pos + 1, pos + 1 + n, cmp);
for (int i = 1; i <= n; i ++) order[pos[i]] = i;
dvc(1, start, start, n);
return ans;
}
