#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
ll id[nx];
ll ans;
struct segtree
{
ll f[4*nx];
ll sm[4*nx];
void update(int l, int r, int i, int idx, ll val)
{
if (idx<l||r<idx) return void();
if (l==r) return f[i]=1, sm[i]=val, void();
int md=(l+r)/2;
update(l, md, 2*i, idx, val);
update(md+1, r, 2*i+1, idx, val);
f[i]=f[2*i]+f[2*i+1];
sm[i]=sm[2*i]+sm[2*i+1];
}
ll query(int l, int r, int i, int cnt)
{
if (l==r) return (cnt==1)?sm[i]:0;
int md=(l+r)/2;
if (f[2*i]>cnt) return query(l, md, 2*i, cnt);
return sm[2*i]+query(md+1, r, 2*i+1, cnt-f[2*i]);
}
} s;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<pair<ll, ll>> v(n);
for (int i=0; i<n; i++) v[i]={attraction[i], i};
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (int i=0; i<n; i++) id[v[i].second]=i;
for (int i=0; i<n; i++)
{
s.update(0, n-1, 1, id[i], attraction[i]);
ans=max(ans, s.query(0, n-1, 1, d-i));
}
return ans;
}
