#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
const int N = (int)1e5 + 7;
struct T {
ll sum;
int cnt;
T() {
sum = cnt = 0;
}
};
int nn;
struct TT {
T tree[N * 4];
void upd(int pos, int val, int v = 1, int l = 0, int r = nn) {
if (l == r) {
if (val == -1) {
tree[v].sum = 0;
tree[v].cnt = 0;
} else {
tree[v].sum = val;
tree[v].cnt = 1;
}
return ;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
upd(pos, val, v + v, l, mid);
} else {
upd(pos, val, v + v + 1, mid + 1, r);
}
tree[v].sum = tree[v + v].sum + tree[v + v + 1].sum;
tree[v].cnt = tree[v + v].cnt + tree[v + v + 1].cnt;
}
ll get(int take, int v = 1, int l = 0, int r = nn) {
if (l == r) {
if (take > 0) {
return tree[v].sum;
} else {
return 0;
}
}
int mid = (l + r) >> 1;
if (tree[v + v + 1].cnt >= take) {
return get(take, v + v + 1, mid + 1, r);
} else {
return get(take - tree[v + v + 1].cnt, v + v, l, mid) + tree[v + v + 1].sum;
}
}
};
TT tr;
vector < ll > a, b, A, B, a1, b1;
ll c[5][N * 3];
bool cmpa(int x, int y) {
return A[x] < A[y];
}
bool cmpb(int x, int y) {
return B[x] < B[y];
}
void divide(int id, int l, int r, int optl, int optr) {
if (l > r) return ;
int opt = optl;
ll best = -1;
int mid = (l + r) >> 1;
for (int i = optl; i <= optr; i++) {
if (id <= 2) {
tr.upd(a1[i], A[i]);
} else {
tr.upd(b1[i], B[i]);
}
ll cost;
if (id & 1 ^ 1) {
cost = tr.get(mid - 2 * (i + 1));
} else {
cost = tr.get(mid - (i + 1));
}
if (cost > best) {
best = cost;
opt = i;
}
}
if (id <= 2) {
for (int i = opt; i <= optr; i++) {
tr.upd(a1[i], -1);
}
} else {
for (int i = opt; i <= optr; i++) {
tr.upd(b1[i], -1);
}
}
divide(id, mid + 1, r, opt, optr);
if (id <= 2) {
for (int i = optl; i <= opt; i++) {
tr.upd(a1[i], -1);
}
} else {
for (int i = optl; i <= opt; i++) {
tr.upd(b1[i], -1);
}
}
divide(id, l, mid - 1, optl, opt);
c[id][mid] = max(best, c[id][mid]);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
nn = n;
for (int i = 0; i < n; i++) {
if (i < start) {
A.pb(attraction[i]);
a.pb(i);
} else if (i > start) {
B.pb(attraction[i]);
b.pb(i - start - 1);
}
}
reverse(all(A));
sort(all(a), cmpa);
sort(all(b), cmpb);
a1.resize(n);
b1.resize(n);
for (int i = 0; i < sz(a); i++)
a1[a[i]] = i;
for (int i = 0; i < sz(b); i++)
b1[b[i]] = i;
if (!a.empty()) {
divide(1, 1, d, 0, sz(a) - 1);
divide(2, 1, d, 0, sz(a) - 1);
}
if (!b.empty()) {
divide(3, 1, d, 0, sz(b) - 1);
divide(4, 1, d, 0, sz(b) - 1);
}
ll ans = 0;
for (int i = 0; i < d; i++) {
ans = max(ans, c[2][i] + attraction[start] + c[3][d - i - 1]);
ans = max(ans, c[1][d - i - 1] + attraction[start] + c[4][i]);
ans = max(ans, c[2][i] + c[3][d - i]);
ans = max(ans, c[1][d - i] + c[4][i]);
}
ans = max(ans, c[2][d] + c[3][0]);
ans = max(ans, c[1][0] + c[4][d]);
return ans;
}
