#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
struct node{
node *L = 0, *R = 0;
int key;
lld sum;
int val, cnt = 1;
node(int v) : key(rand()), sum(v), val(v) { }
void up(){ sum = val, cnt = 1; if(L)sum += L->sum, cnt += L->cnt; if(R)sum += R->sum; }
pair<node*, node*> splitVal(int s){
if(val < s){
if(!L)return{nullptr, this};
auto p = L->splitVal(s);
L = p.ss; up();
return {p.ff, this};
}else{
if(!R)return{this, nullptr};
auto p = R->splitVal(s);
R = p.ff; up();
return {this, p.ss};
}
}
pair<node*, node*> splitSize(int k){
if(k == (L?L->cnt:0)){
auto x = L; L = 0; up();
return {L, this};
}
else if(k < (L?L->cnt:0)){
if(!L)return{nullptr, this};
auto p = L->splitSize(k);
L = p.ss; up();
return {p.ff, this};
}else{
if(!R)return{this, nullptr};
auto p = R->splitSize(k-1-(L?L->cnt:0));
R = p.ff; up();
return {this, p.ss};
}
}
friend node* merge(node* a, node* b){
if(!a)return b;
if(!b)return a;
if(a->key < b->key)
return a->R = merge(a->R, b), a->up(), a;
else
return b->L = merge(a, b->L), b->up(), b;
}
} *root = 0;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
srand(time(0));
lld ans = 0;
for(int i = 0; i < min(n, d); i++){
if(!root)root = new node(attraction[i]);
else{
auto p = root->splitVal(attraction[i]);
root = merge(merge(p.ff, new node(attraction[i])), p.ss);
}
auto p = root->splitSize(d-i);
//cout << d-i << " " << p.ff->sum << endl;
ans = max(ans, p.ff->sum);
root = merge(p.ff, p.ss);
}
return ans;
}
