#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 = 100100;
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) {
turn (1, p);
}
void turnOff (int 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;
if (cnt[2*id] >= x) return get(x, 2*id, le, mid);
else tree[2*id] + get(x-cnt[2*id], 2*id+1, mid+1, ri);
}
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 ();
ll ans = 0;
FOR(i, 0, n-1) {
if (d-i <= 0) break;
turnOn(to[i]);
// cout << " i = " << i << endl;
// cout << " turned on " << to[i] << endl;
ll cur = get(d-i);
// cout << " cur = " << cur << endl;
ans = max(ans, cur);
}
return ans;
}
