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