#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define X first
#define Y second
int n;
int a[100007];
int ord[100007], pos[100007];
struct SegmentTree {
int lv;
vector<int> sum, cnt;
void init(int n) {
lv = 2;
while(lv < n + 2)
lv *= 2;
sum.assign(2 * lv + 2, 0);
cnt.assign(2 * lv + 2, 0);
}
void upd(int w) {
w /= 2;
while(w) {
sum[w] = sum[2 * w] + sum[2 * w + 1];
cnt[w] = cnt[2 * w] + cnt[2 * w + 1];
w /= 2;
}
}
void add(int i) {
//~ cout << "add" << i << endl;
int w = lv + pos[i];
sum[w] = a[i];
cnt[w] = 1;
upd(w);
}
void remove(int i) {
//~ cout << "rm" << i << endl;
int w = lv + pos[i];
sum[w] = 0;
cnt[w] = 0;
upd(w);
}
int query(int w, int l, int r, int k) {
if(r < l || k <= 0)
return 0;
if(cnt[w] <= k)
return sum[w];
return query(2 * w, l, (l + r) / 2, k - cnt[2 * w + 1])
+ query(2 * w + 1, (l + r) / 2 + 1, r, k);
}
int query(int k) {
//~ cout << "query " << k << " = " <<query(1, 0, lv - 1, k) << endl;
return query(1, 0, lv - 1, k);
}
};
SegmentTree ST;
ii l[300007], r[300007];
int st;
void calc(int d1, int d2, int i1, int i2, ii *f, int t) {
if(d2 < d1)
return ;
int dmid = (d1 + d2) / 2;
f[dmid].Y = -1e9;
for(int i = i1 ; i <= i2 ; i++) {
ST.add(i);
if(t * (i - i1) <= dmid)
f[dmid] = max(f[dmid], {ST.query(dmid - t * (i - st)), -i});
}
f[dmid].Y = -f[dmid].Y;
int imid = f[dmid].Y;
//~ cout << imid << endl;
//~ cout << "calc " << d1 << " " << d2 << " " << i1 << " " << i2 << " " << dmid << " " << imid << endl;
for(int i = imid ; i <= i2 ; i++)
ST.remove(i);
calc(dmid + 1, d2, imid, i2, f, t);
for(int i = i1 ; i < imid ; i++)
ST.remove(i);
calc(d1, dmid - 1, i1, imid, f, t);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
int res = 0;
::n = n;
for(int i = 0 ; i < n ; i++)
a[i + 1] = attraction[i];
start++;
for(int tt = 0 ; tt < 2 ; tt++) {
memset(l, 0, sizeof l);
memset(r, 0, sizeof r);
vector<ii> hlp(n);
for(int i = 0 ; i < n ; i++)
hlp[i] = {a[i + 1], i + 1};
sort(hlp.begin(), hlp.end());
for(int i = 0 ; i < n ; i++) {
ord[i + 1] = hlp[i].Y;
pos[hlp[i].Y] = i + 1;
}
ST.init(n);
st = start;
calc(1, d, start, n, r, 2);
if(start > 1) {
start--;
ST.init(n);
reverse(a + 1, a + n + 1);
start = n - start + 1;
for(int i = 0 ; i < n ; i++)
hlp[i] = {a[i + 1], i + 1};
sort(hlp.begin(), hlp.end());
for(int i = 0 ; i < n ; i++) {
ord[i + 1] = hlp[i].Y;
pos[hlp[i].Y] = i + 1;
}
st = start;
calc(1, d, start, n, l, 1);
reverse(a + 1, a + n + 1);
start = n - start + 1;
for(int i = 1 ; i <= d ; i++)
l[i].Y = n + 1 - l[i].Y;
start++;
}
r[0].Y = start;
l[0].Y = start - 1;
//~ cout << "r:\n";
//~ for(int i = 0 ; i <= d ; i++)
//~ cout << i << " " <<r[i].X << " " << r[i].Y << endl;
//~ cout << "l:\n";
//~ for(int i = 0 ; i <= d ; i++)
//~ cout << i << " " <<l[i].X << " " << l[i].Y << endl;
for(int dr = 0 ; dr <= d ; dr++) {
int dl = d - dr - 1;
if(dl >= 0)
res = max(res, r[dr].X + l[dl].X);
}
res = max(res, r[d].X);
reverse(a + 1, a + n + 1);
start = n + 1 - start;
}
return res;
}
