#include <bits/stdc++.h>
#include "holiday.h"
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 2;
const int maxD = 250001;
int n;
vector <ll> node;
struct __attribute__((packed)) TNode{
TNode *lp, *rp;
int val;
ll sum;
TNode(int _val, ll _sum) : lp(nullptr), rp(nullptr), val(_val), sum(_sum){}
TNode(TNode* left, TNode* right){
lp = left, rp = right;
val = sum = 0;
if (lp){
val += lp->val;
sum += lp->sum;
}
if (rp){
val += rp->val;
sum += rp->sum;
}
}
};
TNode* root[maxN];
int p[maxN];
pll ls[maxD];
pll rs[maxD];
int Start;
TNode* build(int i, int l = 1, int r = node.size()){
if (l == r){
if (l == i) return new TNode(1, node[i - 1]);
return new TNode(0, 0ll);
}
int mid = (l + r) / 2;
return new TNode(build(i, l, mid), build(i, mid + 1, r));
}
TNode* update(TNode* id, int i, int l = 1, int r = node.size()){
if (l == r){
return new TNode(id->val + 1, id->sum + node[l - 1]);
}
int mid = (l + r) / 2;
if (i <= mid) return new TNode(update(id->lp, i, l, mid), id->rp);
else return new TNode(id->lp, update(id->rp, i, mid + 1, r));
}
ll get(TNode* id, int k, int l = 1, int r = node.size()){
if (l == r){
return k * node[l - 1];
}
int mid = (l + r) / 2;
if (id->rp->val >= k) return get(id->rp, k, mid + 1, r);
else return id->rp->sum + get(id->lp, k - id->rp->val, l, mid);
}
inline int pos(int i){
return upper_bound(node.begin(), node.end(), i) - node.begin();
}
void DnCl(int s, int t, int l, int r){
if (l > r || s < t){
return;
}
int mid = (l + r) / 2;
for (int i = s; i >= t; --i){
ll tem = get(root[i], min(mid - (Start - i - 1), root[i]->val));
if (tem > ls[mid].fi){
ls[mid].fi = tem;
ls[mid].se = i;
}
}
if (l == r) return;
DnCl(s, ls[mid].se, l, mid - 1);
DnCl(ls[mid].se, t, mid + 1, r);
}
void DnCr(int s, int t, int l, int r){
if (l > r || s > t){
return;
}
int mid = (l + r) / 2;
for (int i = s; i <= t; ++i){
ll tem = get(root[i], min(mid - (i - Start), root[i]->val));
if (tem > rs[mid].fi){
rs[mid].fi = tem;
rs[mid].se = i;
}
}
if (l == r) return;
DnCr(s, rs[mid].se, l, mid - 1);
DnCr(rs[mid].se, t, mid + 1, r);
}
ll findMaxAttraction(int N, int start, int d, int attraction[]){
n = N;
for (int i = 0; i < n; ++i){
p[i + 1] = attraction[i];
node.pb(p[i + 1]);
}
if (d == 0) return 0;
node.pb(0);
sort(node.begin(), node.end());
node.resize(unique(node.begin(), node.end()) - node.begin());
++start;
root[start] = build(pos(p[start]));
root[start - 1] = build(pos(p[start - 1]));
for (int i = start + 1; i <= n; ++i){
root[i] = update(root[i - 1], pos(p[i]));
}
for (int i = start - 2; i >= 1; --i){
root[i] = update(root[i + 1], pos(p[i]));
}
Start = start;
DnCr(start, n, 1, d);
DnCl(start - 1, 1, 1, d);
ll ans = ls[d - 1].fi;
for (int i = 1; i <= d; ++i){
int k = d - rs[i].se + start - 1 - i;
if (k < 0) ans = max(ans, rs[i].fi);
else ans = max(ans, ls[k].fi + rs[i].fi);
}
ans = max(ans, rs[d - 1].fi);
for (int i = 1; i <= d; ++i){
int k = d + ls[i].se - start - i - 1;
if (k < 0) ans = max(ans, ls[i].fi);
else ans = max(ans, ls[i].fi + rs[k].fi);
}
ofstream out("test.out");
out << ans;
out.close();
return ans;
}
