#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
typedef long long int ll;
struct node{
node *lc = NULL;
node *rc = NULL;
int L = 0,R = 0;
ll sum = 0;
void calc(){
sum = 0;
if(lc)sum+=lc->sum;
if(rc)sum+=rc->sum;
}
ll query(int l,int r){
if(l==L && r==R)return sum;
int tm = (L+R)/2;
if(r<=tm && lc)return lc->query(l,r);
if(l>tm && rc)return rc->query(l,r);
if(l<=tm && r>tm){
ll res = 0;
if(lc)res+=lc->query(l,tm);
if(rc != NULL)res+=rc->query(tm+1,r);
return res;
}
return 0;
}
node(){}
node(node *v){
lc = v->lc;
rc = v->rc;
L = v->L;
R = v->R;
sum = v->sum;
}
node(int _L,int _R){
L = _L;
R = _R;
}
};
node *upd(node *v,int pos,int x){
if(v->L == v->R){
node *res = new node(v);
res->sum+=x;
return res;
}
int tm = (v->L+v->R)/2;
if(!v->lc)v->lc = new node(v->L,tm);
if(!v->rc)v->rc = new node(tm+1,v->R);
node *res = new node(v);
if(tm>=pos)res->lc = upd(v->lc,pos,x);
else res->rc = upd(v->rc,pos,x);
res->calc();
return res;
}
long long int findMaxAttraction(int n, int start, int d, int a[]) {
ll ans = 0;
if(start==0){
d++;
vector<node*>val;
vector<int>cnt(101,0);
for(int i=0;i<n;i++){
d--;
if(d<=0)break;
cnt[a[i]]++;
if(!i)val.push_back(new node(0,100000));
val.push_back(upd(val.back(),a[i],a[i]));
int tot = 0;
for(int j=100;j>=0;j--){
tot+=cnt[j];
if(tot >= d || j == 0){
ll c = val.back()->query(j,100);
c-=(tot-d) * j;
ans = max(ans,c);
break;
}
}
}
}
return ans;
}
