#include "holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll value[maxn], d;
ll arr[maxn];
class node {
public:
ll sum, cnt, lb, rb;
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;
}
};
node* build(int li=1, int ri=d) {
if(li == ri) return new node(0LL, 0LL);
else {
int mid = (li + ri) / 2;
return new node(build(li, mid), build(mid+1, ri));
}
}
node* update(node *curr, ll uind, ll uval, int li=1, int ri=d) {
if(li == ri) {
return new node(curr->sum + uval, curr->cnt + 1);
}
else {
int mid = (li + ri) / 2;
if(uind <= mid) return new node(update(curr->leftchild, uind, uval, li, mid), curr->rightchild);
else return new node(curr->leftchild, update(curr->rightchild, uind, uval, mid+1, ri));
}
}
ll solve(node *p, node *pm, ll k, int li=1, int ri=d) {
ll total = p->cnt - pm->cnt;
if(total < k) return (p->sum - pm->sum);
if(li == ri) {
return k * value[li];
}
else {
int mid = (li + ri) / 2;
ll total_right = p->rightchild->cnt - pm->rightchild->cnt;
if(total_right >= k) return solve(p->rightchild, pm->rightchild, k, mid+1, ri);
else return (p->rightchild->sum - pm->rightchild->sum) + solve(p->leftchild, pm->leftchild, k - total, li, mid);
}
}
node *prefix[maxn];
set<int>st;
map<int,int>ind;
long long int findMaxAttraction(int n, int start, int c, int attraction[]) {
start++;
for(int i=0;i<n;i++) {
st.insert(attraction[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[attraction[i]];
}
node *curr = build();
prefix[0] = curr;
for(int i=1;i<=n;i++) {
curr = update(curr, arr[i], value[arr[i]]);
prefix[i] = curr;
}
ll result = 0LL;
for(int i=1;i<=start;i++) {
for(int j=start;j<=n;j++) {
ll walk = j - i + min(start - i, j - start);
//cout<<i<<" - "<<j<<" walking: "<<walk<<"\n";
result = max(result, solve(prefix[j], prefix[i-1], c - walk));
}
}
return result;
}
