#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
typedef long long int ll;
ll t[4*MAXN];
int cnt[4*MAXN];
void upd(int v,int pos,int l,int r,int val,int c){
if(l==r){
t[v] = val;
cnt[v] = c;
return;
}
int tm = (l+r)/2;
if(pos<=tm)upd(2*v,pos,l,tm,val,c);
else upd(2*v+1,pos,tm+1,r,val,c);
t[v] = t[2*v] + t[2*v+1];
cnt[v] = cnt[2*v] + cnt[2*v+1];
}
ll query(int v,int l,int r,int k){
if(cnt[v] == k || l==r)return t[v];
int tm = (l+r)/2;
if(cnt[2*v+1] >= k)return query(2*v+1,tm+1,r,k);
else return t[2*v+1] + query(2*v,l,tm,k-cnt[2*v+1]);
}
long long int findMaxAttraction(int n, int start, int d, int a[]) {
ll ans = 0;
vector<pair<int,int>>b;
for(int i=0;i<n;i++)b.push_back({a[i],i});
sort(b.begin(),b.end());
vector<int>idx(n);
for(int i=0;i<n;i++)idx[b[i].second] = i;
if(start==0){
d++;
for(int i=0;i<n;i++){
d--;
if(!d)break;
upd(1,idx[i]+1,1,n,a[i],1);
ans = max(ans,query(1,1,n,d));
}
}
return ans;
}
