#include <bits/stdc++.h>
#include "holiday.h"
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100500;
ll value[maxn], d;
int arr[maxn];
/*class node {
public:
ll sum;
int cnt;
node *leftchild, *rightchild;
node(ll _sum, ll _cnt) {
sum = _sum;
cnt = _cnt;
}
node(node *a, node *b) {
leftchild = a;
rightchild = b;
sum = a->sum + b->sum;
cnt = a->cnt + b->cnt;
}
};*/
vector<ll>sum, cnt, l, r;
int makenewleaf(ll _sum, ll _cnt) {
sum.pb(_sum);
cnt.pb(_cnt);
l.pb(-1);
r.pb(-1);
return int(sum.size()-1);
}
int makenewparent(int _l, int _r) {
sum.pb(sum[_l] + sum[_r]);
cnt.pb(cnt[_l] + cnt[_r]);
l.pb(_l);
r.pb(_r);
return int(sum.size()-1);
}
int zeroleaf;
int build(int li=1, int ri=d) {
if(li == ri) return zeroleaf;
else {
int mid = (li + ri) / 2;
return makenewparent(build(li, mid), build(mid+1, ri));
}
}
int update(int curr, ll uind, ll uval, int li=1, int ri=d) {
if(li == ri) {
return makenewleaf(sum[curr] + uval, cnt[curr] + 1);
}
else {
int mid = (li + ri) / 2;
if(uind <= mid) return makenewparent(update(l[curr], uind, uval, li, mid), r[curr]);
else return makenewparent(l[curr], update(r[curr], uind, uval, mid+1, ri));
}
}
ll solve(int p, int pm, ll k, int li=1, int ri=d) {
ll total = cnt[p] - cnt[pm];
//cout<<li<<" "<<ri<<" -> "<<total<<", "<<k<<"\n";
if(k == 0) return 0LL;
if(total < k) return (sum[p] - sum[pm]);
if(li == ri) {
return k * value[li];
}
else {
int mid = (li + ri) / 2;
ll total_right = cnt[r[p]] - cnt[r[pm]];
if(total_right >= k) return solve(r[p], r[pm], k, mid+1, ri);
else return (sum[r[p]] - sum[r[pm]]) + solve(l[p], l[pm], k - total_right, li, mid);
}
}
int prefix[maxn];
set<int>st;
map<int,int>ind;
int n, start, c;
ll dp[maxn];
void solvedp(int l=1, int r=start, int optl=start, int optr=n) {
if(l > r) return;
int mid = (l + r) / 2;
// calculate dp[mid]
dp[mid] = -1;
int optmid = -1;
for(int i=optl;i<=optr;i++) {
ll walk = i - mid + min(start - mid, i - start);
ll curr = solve(prefix[i], prefix[mid-1], max(0LL, c - walk));
if(curr > dp[mid]) {
dp[mid] = curr;
optmid = i;
}
}
solvedp(l, mid-1, optl, optmid);
solvedp(mid+1, r, optmid, optr);
}
ll findMaxAttraction(int _n, int _start, int _c, int _attractions[]) {
//ifstream fin("input.txt");
n = _n;
start = _start;
c = _c;
//cin>>n>>start>>c;
start++;
for(int i=0;i<n;i++) {
arr[i] = _attractions[i];
st.insert(arr[i]);
}
int br = 1;
for(int i:st) {
value[br] = i;
ind[i] = br++;
}
d = br - 1;
for(int i=n-1;i>=0;i--) {
arr[i+1] = ind[arr[i]];
}
zeroleaf = makenewleaf(0LL, 0LL);
int curr = build();
prefix[0] = curr;
for(int i=1;i<=n;i++) {
prefix[i] = prefix[i-1];
prefix[i] = update(prefix[i], arr[i], value[arr[i]]);
//cout<<i<<": "<<sum[prefix[i]]<<"\n";
}
//cout<<solve(prefix[4], prefix[0], 3)<<"A\n";
solvedp();
ll result = 0LL;
for(int i=1;i<=n;i++) {
result = max(result, dp[i]);
}
return result;
}
