#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
struct node{
int l, r;
ll val;
int cnt;
node *lft, *rht;
node (int tl, int tr): l(tl), r(tr), val(0), cnt(0) {
if (l + 1 == r) {
lft = rht = NULL;
return;
}
lft = new node(l, (l + r) / 2);
rht = new node((l + r) / 2, r);
}
void upd(int p, int x) {
if (p < l || p >= r) return;
if (l + 1 == r) {
val += x;
cnt = (bool) val;
return;
}
lft->upd(p, x);
rht->upd(p, x);
val = lft->val + rht->val;
cnt = lft->cnt + rht->cnt;
}
ll qry(int& x) {
if (x <= 0) return 0;
if (x >= cnt) {
x -= cnt;
return val;
}
ll tmp = rht->qry(x);
return tmp + lft->qry(x);
}
}* root;
int strt, d;
int pos[100069], val[100069];
int cl = 0, cr = 0;
bool flpd[100069];
void flp(int x) {
if (flpd[x]) root->upd(pos[x], -val[x]);
else root->upd(pos[x], val[x]);
flpd[x] ^= 1;
}
void st(int tl, int tr) {
if (tl > tr) swap(tl, tr);
while (cl > tl) flp(--cl);
while (cl < tl) flp(cl++);
while (cr > tr) flp(cr--);
while (cr < tr) flp(++cr);
}
ll fnd(int l, int r, int sl, int sr) {
if (r < l) return 0;
int m = (l + r) / 2;
pair<ll, int> maxi = {INT_MIN, -1};
for (int i = sl; i <= sr; i++) {
st(m, i);
int tmp = d - abs(strt - m) - abs(m - i);
ll vl = tmp;
if (tmp > 0) vl = root->qry(tmp); //let's hope this works
//cout<<m<<':'<<i<<'!'<<vl<<'?'<<root->val<<endl;
maxi = max(maxi, {vl, i});
}
return max(maxi.f, max(fnd(l, m - 1, sl, maxi.s), fnd(m + 1, r, maxi.s, sr)));
}
long long int findMaxAttraction(int n, int start, int D, int attraction[]) {
strt = start; d = D;
vector<pair<int, int>> srt;
for (int i = 0; i < n; i++) {
val[i] = attraction[i];
srt.push_back({val[i], i});
}
sort(all(srt));
for (int i = 0; i < n; i++) {
pos[srt[i].s] = i;
}
root = new node(0, n);
flp(0);
return max(fnd(0, strt, 0, n - 1), fnd(strt, n - 1, 0, n - 1));
}
