#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
struct node {
int l, r;
ll cnt, val;
node *left, *right;
node(int l, int r, int c = 0, ll v = 0) : l(l), r(r), cnt(c), val(v) {}
~node() {
delete left;
delete right;
}
void merge() {
cnt = left->cnt + right->cnt;
val = left->val + right->val;
}
void build() {
if(l != r) {
int m = (l + r) / 2;
left = new node(l, m);
right = new node(m + 1, r);
left->build();
right->build();
}
}
node* upd(int p, ll v) {
if(l == r)
return new node(l, r, 1, v);
node* result = new node(l, r);
int m = (l + r) / 2;
result->left = (p <= m ? left->upd(p, v) : left);
result->right = (p > m ? right->upd(p, v) : right);
result->merge();
return result;
}
ll bsum(ll amt) {
//cerr << amt << " " << l << " " << r << endl;
if(amt == 0)
return 0;
if(amt >= cnt)
return val;
if(amt <= right->cnt)
return right->bsum(amt);
return right->val + left->bsum(amt - right->cnt);
}
void dbg() {
//cerr << "[" << l << ", " << r << "] cnt = " << cnt << " val = " << val << endl;
if(l < r) {
left->dbg();
right->dbg();
}
}
};
vector<node*> trees;
void solve(vector<ll> &dp, vector<ll> &opt, int L, int R, int oL, int oR) {
//cerr << "Solving [" << L << ", " << R << "] [" << oL << ", " << oR << "]" << endl;
if(L > R)
return;
int m = (L + R) / 2;
ll cur = -1;
int cut = 0;
for(int rest = oL; rest <= min(oR, m); rest++) {
//cerr << "Querying tree " << rest << endl;
ll res = trees[rest]->bsum(m - rest);
if(res > cur) {
cur = res;
cut = rest;
}
}
dp[m] = cur;
opt[m] = cut;
solve(dp, opt, L, m - 1, oL, cut);
solve(dp, opt, m + 1, R, cut, oR);
}
void extreme(vector<ll> &at, vector<ll> &dp, vector<ll> &opt) {
int n = at.size();
dp.resize(2*n);
opt.resize(2*n);
vector<ii> pas(n);
for(int i = 0; i < n; i++)
pas[i] = {at[i], i};
sort(pas.begin(), pas.end());
//for(int i = 0; i < n; i++)
// cerr << pas[i].first << " " << pas[i].second << endl;
vector<ii> comp(n);
for(int i = 0; i < n; i++)
comp[pas[i].second] = ii{i, pas[i].first};
//for(int i = 0; i < n; i++)
// cerr << comp[i].first << " " << comp[i].second << endl;
node* ini = new node(0, n - 1);
ini->build();
trees.push_back(ini->upd(comp[0].first, comp[0].second));
for(int i = 1; i < n; i++)
trees.push_back(trees.back()->upd(comp[i].first, comp[i].second));
//for(int i = 0; i < n; i++) {
//cerr << "TREE " << i << "\n===\n";
//trees[i]->dbg();
//cerr << "===" << endl;
//}
solve(dp, opt, 0, 2*n, 0, n - 1);
for(auto &t : trees)
delete t;
delete ini;
//cerr << "SOLVED" << endl;
//for(int i = 0; i < 2*n; i++) {
// cerr << i << " " << dp[i] << " " << opt[i] << endl;
//}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if(start != 0)
return 0;
vector<ll> dp, opt, at;
at.resize(n);
for(int i = 0; i < n; i++)
at[i] = attraction[i];
extreme(at, dp, opt);
//cerr << "GOOD" << endl;
//cerr << dp.size() << " " << opt.size() << endl;
//for(int i = 0; i < dp.size(); i++) {
// assert(i < opt.size());
// cerr << i << " " << dp[i] << " " << opt[i] << endl;
//}
return dp[min(d, 2*n - 1)];
}
