#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5;
struct node {
int cnt, sum;
node* L;
node* R;
node() {
cnt = sum = 0;
L = R = nullptr;
}
};
int n, s, d, a[N];
pair<int, int> b[N];
node* root[N];
node* merge(node* x, node* y) {
node* z = new node();
z->cnt = x->cnt + y->cnt;
z->sum = x->sum + y->sum;
return z;
}
node* build(int l=0, int r=n-1) {
node* p = new node();
if (l == r) {
if (l == b[0].second) {
p->cnt = 1;
p->sum = b[0].first;
}
return p;
}
int mid = (l+r) >> 1;
p->L = build(l, mid);
p->R = build(mid+1, r);
p->cnt = p->L->cnt + p->R->cnt;
p->sum = p->L->sum + p->R->sum;
return p;
}
node* update(int idx, int x, node* root, int l=0, int r=n-1) {
node* p = new node();
if (l == r) {
p->cnt = 1;
p->sum = x;
return p;
}
int mid = (l+r) >> 1;
if (idx <= mid) {
p->L = update(idx, x, root->L, l, mid);
p->R = root->R;
}
else {
p->L = root->L;
p->R = update(idx, x, root->R, mid+1, r);
}
p->cnt = p->L->cnt + p->R->cnt;
p->sum = p->L->sum + p->R->sum;
return p;
}
node* query(int a, int b, node* root, int l=0, int r=n-1) {
if (a <= l && r <= b) {
return root;
}
int mid = (l+r) >> 1;
if (b <= mid) {
return query(a, b, root->L, l, mid);
}
else if (mid+1 <= a) {
return query(a, b, root->R, mid+1, r);
}
else {
return merge(query(a, b, root->L, l, mid), query(a, b, root->R, mid+1, r));
}
}
int c(int a, int b) {
int x = b-a + min(s-a, b-s);
if (x >= d) return 0;
x = min(d-x, b-a+1);
int l = 0;
int r = n-1 - (b-a+1 - x);
while (l < r) {
int mid = (l+r) >> 1;
if (query(a, b, root[mid])->cnt >= x) r = mid;
else l = mid+1;
}
return query(a, b, root[l])->sum;
}
int findMaxAttraction(signed N, signed S, signed D, signed attraction[]) {
n = N;
s = S;
d = D;
for (int i = 0; i < n; i++) {
a[i] = attraction[i];
b[i] = make_pair(a[i], i);
}
sort(b, b+n);
reverse(b, b+n);
root[0] = build();
for (int i = 1; i < n; i++) {
root[i] = update(b[i].second, b[i].first, root[i-1]);
}
int ans = 0;
int r = n-1;
for (int l = s; l >= 0; l--) {
while (r-1 >= s && c(l, r-1) >= c(l, r)) r--;
ans = max(ans, c(l, r));
}
return ans;
}
