#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << "\n"
#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define MAX_N 100003
#define atracciones first
#define pos second
#define activas first
#define suma second
int lugar[MAX_N], offset, tmp;
vector<pair<int, int> > sortedatt;
pair<lli, lli> st[1 << 18];
lli optr[MAX_N * 2], optl[MAX_N * 2], maxr[MAX_N * 2], maxl[MAX_N * 2], res, avl, avr;
lli queryst(int nodo, int k){
if (!k) return 0;
if (st[nodo].activas <= k) return st[nodo].suma;
if (st[nodo * 2].activas > k) return queryst(nodo * 2, k);
else return st[nodo * 2].suma + queryst(nodo * 2 + 1, k - st[nodo * 2].activas);
}
void updatest(int p){
st[offset + p].activas = 1;
st[offset + p].suma = sortedatt[p].atracciones;
p += offset;
while (p > 0){
p >>= 1;
st[p].activas = st[p * 2].activas + st[p * 2 + 1].activas;
st[p].suma = st[p * 2].suma + st[p * 2 + 1].suma;
}
}
void initst(){
rep(i, 0, offset * 2 - 1) st[i] = {0,0};
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
rep(i, 0, n - 1) sortedatt.emplace_back(attraction[i], i);
sort(sortedatt.begin(), sortedatt.end());
reverse(sortedatt.begin(), sortedatt.end());
rep(i, 0, n - 1) lugar[sortedatt[i].pos] = i;
offset = 1;
while (offset < n) offset <<= 1;
initst();
rep(ciudad, 0, n - start + 1){
updatest(lugar[start + ciudad]);
rep(att, 1, min(ciudad + 1, (lli)d)){
tmp = queryst(1, att);
if (tmp > optr[ciudad + att]){
optr[ciudad + att] = tmp;
maxr[ciudad + att] = ciudad;
}
}
}
initst();
rep(ciudad, 1, start){
updatest(lugar[start - ciudad]);
rep(att, 1, min(ciudad + 1, (lli)d)){
tmp = queryst(1, att);
if (tmp > optl[ciudad + att]){
optl[ciudad + att] = tmp;
maxl[ciudad + att] = ciudad;
}
}
}
res = 0;
rep(i, 0, d){
// si va primero a la izquierda
avl = maxl[i] + i;
if (avl <= d) res = max(res, optl[i] + optr[d - avl]);
// si va primero a la derecha
avr = maxr[i] + i;
if (avr <= d) res = max(res, optr[i] + optl[d - avr]);
}
return res;
}
