#include"holiday.h"
// #include "grader.cpp"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct node {
int active=0;
ll sm=0;
void merge(const node& o) {
active+=o.active;
sm+=o.sm;
}
friend node merge(node a, const node& b) {
a.merge(b);
return a;
}
};
vi cs;
struct segtree {
int ptwo;
vector<node> seg;
segtree(){}
node& operator[](int i) {
return seg[i+ptwo];
}
segtree(int nn) {
ptwo=1;
while(ptwo<nn) ptwo*=2;
seg.resize(ptwo*2);
}
ll good(int d) {
if(d<0) return -oo;
int at=1;
ll ans=0;
while(at<ptwo) {
at*=2;
if(seg[at+1].active<d) {
ans+=seg[at+1].sm;
d-=seg[at+1].active;
} else at++;
}
return ans+min(seg[at].sm,cs[at-ptwo]*ll(d));
}
void update(int i, int val, int sgn) {
assert(i>=0 and i<ptwo);
i+=ptwo;
seg[i].sm+=sgn*val;
seg[i].active+=sgn;
for(i/=2;i>=1;i/=2) {
seg[i] = merge(seg[2*i],seg[2*i+1]);
}
}
void build() {
for(int i=ptwo-1;i>=1;--i) {
seg[i] = merge(seg[2*i],seg[2*i+1]);
}
}
};
segtree seg;
ll ans=0;
void solve(int l, int r, int a, int b, int d, int atr[]) {
if(a>b or l>r) return;
int mid = (l+r)/2;
pair<ll,int> opt;
if(d>=r-mid+1) {
d++;
for(int i=mid;i<=r;++i) {
d--;
seg.update(atr[i],cs[atr[i]],1);
}
opt = {seg.good(d),a};
for(int i=a+1;i<=b;++i) {
seg.update(atr[i],cs[atr[i]],1);
d-=2;
opt = max(opt,{seg.good(d),i});
}
ans = max(ans,opt.first);
for(int i=a+1;i<=b;++i) {
seg.update(atr[i],cs[atr[i]],-1);
d+=2;
}
solve(l,mid-1,a,opt.second,d-1,atr);
for(int i=mid;i<=r;++i) {
d++;
seg.update(atr[i],cs[atr[i]],-1);
}
d--;
}
for(int i=a+1;i<=opt.second;++i) {
seg.update(atr[i],cs[atr[i]],1);
d-=2;
}
solve(mid+1,r,opt.second,b,d,atr);
for(int i=a+1;i<=opt.second;++i) {
seg.update(atr[i],cs[atr[i]],-1);
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
ans=0;
cs = vi(attraction,attraction+n);
sort(all(cs));
cs.erase(unique(all(cs)),cs.end());
for(int i=0;i<n;++i) {
attraction[i] = lower_bound(all(cs),attraction[i])-cs.begin();
}
seg = segtree(cs.size());
for(int rep=0;rep<2;++rep) {
solve(0,start,start,n-1,d,attraction);
reverse(attraction,attraction+n);
start=n-1-start;
}
return ans;
}
