#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<int> vi;
const int MAXN = 500100;
ll a[MAXN];
int n;
vector<pair<ll, int>> srt;
int to[MAXN];
ll tree[4*MAXN], cnt[4*MAXN];
void build (int id = 1, int le = 0, int ri = n-1) {
if (le == ri) {
tree[id] = 0;
cnt[id] = 0;
return;
}
int mid = (le+ri)/2;
build (2*id, le, mid);
build (2*id+1, mid+1, ri);
tree[id] = tree[2*id] + tree[2*id+1];
cnt[id] = cnt[2*id] + cnt[2*id+1];
}
void turn (bool on, int p, int id = 1, int le = 0, int ri = n-1) {
if (le == ri) {
if (on) {
tree[id] = srt[le].f;
cnt[id] = 1;
} else {
tree[id] = 0;
cnt[id] = 0;
}
return;
}
int mid = (le+ri)/2;
if (p <= mid)
turn (on, p, 2*id, le, mid);
else
turn (on, p, 2*id+1, mid+1, ri);
tree[id] = tree[2*id] + tree[2*id+1];
cnt[id] = cnt[2*id] + cnt[2*id+1];
}
void turnOn (int p) {
p = to[p];
turn (1, p);
}
void turnOff (int p) {
p = to[p];
turn (0, p);
}
ll get (int x, int id = 1, int le = 0, int ri = n-1) {
if (x <= 0) return 0;
if (cnt[id] <= x) return tree[id];
int mid = (le+ri)/2;
return get(x, 2*id, le, mid) + get(x-cnt[2*id], 2*id+1, mid+1, ri);
}
ll f[MAXN], ansF[MAXN];
ll rec (int le, int ri, int fr, int to, int moved = 0) {
int m = (le+ri)/2;
ansF[m] = -1;
FOR(i, fr, to) {
int remD = m - moved - (i-fr);
if (remD <= 0) break;
turnOn(i);
ll cur = get(remD);
if (cur > ansF[m]) {
ansF[m] = cur;
f[m] = i;
}
}
if (ansF[m] == -1) {
ansF[m] = 0;
f[m] = fr;
}
FOR(i, fr, to) turnOff(i);
if (le <= m-1) rec(le, m-1, fr, f[m], moved);
FOR(i, fr, f[m]-1) {
moved++;
turnOn(i);
}
if (m+1 <= ri) rec(m+1, ri, f[m], to, moved);
FOR(i, fr, f[m]-1) {
moved--;
turnOff(i);
}
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
n = N;
FOR(i, 0, n-1) a[i] = attraction[i];
FOR(i, 0, n-1) {
srt.pb({a[i], i});
}
sort(srt.begin(), srt.end());
reverse(srt.begin(), srt.end());
FOR(i, 0, n-1) {
to[srt[i].s] = i;
}
build ();
rec(0, d, 0, n-1);
//FOR(i, 0, d) cout << " i = " << i << " f(i) = " << f[i] << " ansF(i) = " << ansF[i] << endl;
ll ans = ansF[d];
return ans;
}
