#pragma GCC optimize ("O3")
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
struct Treap {
struct Node {
lint sum; // sum of all nodes in subtree
lint val; // real value, constant
int cnt; // size of subtree
int prior; // priority
Node *l, *r;
Node(lint v = 0): val(v), prior(rand()), l(NULL), r(NULL), cnt(1), sum(v) {}
void update() {
sum = val;
cnt = 1;
if (l) sum += l->sum, cnt += l->cnt;
if (r) sum += r->sum, cnt += r->cnt;
}
};
using node = Node *;
node root;
void split(node t, node &l, node &r, int key, int add) { // implicit split, l is key-largest elements
int cur_key = add + ((t && t->l)? t->l->cnt : 0) + 1;
if (!t)
l = r = NULL;
else if (key < cur_key)
split(t->l, l, t->l, key, add), r = t;
else
split(t->r, t->r, r, key, cur_key), l = t;
if (t) t->update();
}
void split(node t, node &l, node &r, lint key) { // split based on value
if (!t)
l = r = NULL;
else if (key >= t->val)
split(t->l, l, t->l, key), r = t;
else
split(t->r, t->r, r, key), l = t;
if (t) t->update();
}
void merge(node &t, node l, node r) {
if (!l || !r)
t = (l)? l : r;
else if (l->prior > r->prior)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
if (t) t->update();
}
void print(node t) {
if (!t) return;
print(t->l);
cout << t->val << " ";
print(t->r);
}
void print() {
cout << "Treap is ";
print(root);
cout << "\n";
}
void insert(lint x) { // insert value x to the tree
node l, r;
split(root, l, r, x);
merge(l, l, new Node(x));
merge(root, l, r);
}
lint query(int d) { // find sum of d-largest elements in tree
node t1, t2;
split(root, t1, t2, d, 0);
lint res = (t1)? t1->sum : 0;
merge(root, t1, t2);
return res;
}
void erase(node &t, lint x) {
if (!t)
return;
else if (t->val == x)
merge(t, t->l, t->r);
else if (t->val < x)
erase(t->l, x);
else
erase(t->r, x);
if (t) t->update();
}
void erase(lint x) {
erase(root, x);
}
void clear(node &t) {
if (!t) return;
clear(t->l), clear(t->r);
t = NULL;
}
void clear() {
clear(root);
}
};
struct Query {
int sl, sr; // startpoints to be computed
int el, er; // possible endpoints to be computed
};
lint findMaxAttraction(int N, int start, int D, int attraction[]) {
Treap treap;
lint res = 0;
deque<Query> q;
q.push_back({0, start, start, N - 1});
int ptl = 0, ptr = 0; // left pointer and right pointer
for (int ptl = 0, ptr = 0; !q.empty(); q.pop_front()) {
int start_l = q.front().sl, start_r = q.front().sr;
int end_l = q.front().el, end_r = q.front().er;
int start_mid = (start_l + start_r) / 2;
int end_mid = -1;
if (start_l > start_r) continue;
if (ptl > start_mid) {
treap.clear();
q.push_front({start_l, start_r, end_l, end_r});
ptl = ptr = 0;
continue;
}
while (ptr <= start_mid && ptr < N) treap.insert(attraction[ptr++]);
while (ptl < start_mid && ptl < N) treap.erase(attraction[ptl++]);
lint cur_opt = -1;
for (lint i = end_l; i <= end_r; i++) {
while (ptr <= i && ptr < N) treap.insert(attraction[ptr++]);
int cnt = D - (i - start_mid) - min(start - start_mid, (int)i - start);
lint now = treap.query(cnt);
if (now > cur_opt) cur_opt = now, end_mid = i;
}
res = max(res, cur_opt);
q.push_back({start_l, start_mid - 1, end_l, end_mid});
q.push_back({start_mid + 1, start_r, end_mid, end_r});
}
return res;
}
