#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int N = 1e5 + 5, maxn = 1e9;
int n, st, d, a[N];
struct node {
int sum;
long long val;
node *left, *right;
node() {
sum = 0, val = 0;
left = right = nullptr;
}
};
node *t[N];
int sum(node *p) {
return p ? p->sum : 0;
}
long long val(node *p) {
return p ? p->val : 0;
}
void upd(node *x, int l, int r, int pos) {
if(l == r) {
x->sum += 1;
x->val += pos;
// cout << l << " " << r << " " << sum(x) << " ^^\n";
return ;
}
int mid = l + r >> 1;
if(pos <= mid) {
x->left = x->left ? new node(*x->left) : new node();
upd(x->left, l, mid, pos);
}
else {
x->right = x->right ? new node(*x->right) : new node();
upd(x->right, mid + 1, r, pos);
}
x->sum = sum(x->left) + sum(x->right);
x->val = val(x->left) + val(x->right);
// cout << l << " " << r << " " << sum(x) << " ^^\n";
}
long long get(node *sl, node *sr, int l, int r, int k) {
int ret = 0;
if(l == r) {
ret = l * min(k, sum(sr->right) - sum(sl->right));
return ret;
}
int mid = l + r >> 1;
int num = sum(sr->right) - sum(sl->right);
if(num > k) {
sl->right = sl->right ? new node(*sl->right) : new node();
sr->right = sr->right ? new node(*sr->right) : new node();
ret = get(sl->right, sr->right, mid + 1, r, k);
return ret;
}
sl->left = sl->left ? new node(*sl->left) : new node();
sr->left = sr->left ? new node(*sr->left) : new node();
ret = val(sr->right) - val(sl->right) + get(sl->left, sr->left, l, mid, k - num);
return ret;
}
long long f(int k) {
int rest = d - k, lim = max(1, st - rest);
long long ret = 0;
for(int i = st; i >= lim; i--) {
int l = st, r = n, mid, j = 0;
while (l <= r) {
mid = l + r >> 1;
int cost = min(mid - st, st - i) + mid - i + k;
if(cost <= d) l = mid + 1, j = mid;
else r = mid - 1;
// cout << i << " " << mid << " " << cost << " ^^\n";
}
// cout << i << " " << j << " " << min(j - st, st - i) + j - i + k << "\n";
if(j) ret = max(ret, get(t[i - 1], t[j], 0, maxn, k));
}
return ret;
}
long long findMaxAttraction(int N, int Start, int D, int a[]) {
t[0] = new node();
n = N, d = D, st = Start;
for(int i = 1; i <= n; i++) {
t[i] = new node(*t[i - 1]);
upd(t[i], 0, maxn, a[i - 1]);
}
// long long ret = f(3);
int l = 1, r = d, m;
while (r - l > 4) {
m = l + r >> 1;
if(f(m) < f(m + 1)) l = m;
else r = m + 1;
}
long long ret = 0;
for(int i = l; i <= r; i++)
// cout << i << " " << f(i) << "\n",
ret = max(ret, f(i));
return ret;
}
//main () {
// cin.tie(0)->sync_with_stdio(0);
// if(fopen("task.inp", "r")) {
// freopen("task.inp", "r", stdin);
// freopen("wa.out", "w", stdout);
// }
// cin >> n >> st >> d;
// for(int i = 0; i < n; i++) cin >> a[i];
// cout << findMaxAttraction(n, st, d, a);
//}
