#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int br;
long long sum;
Node(){};
Node(int br, long long sum) : br(br), sum(sum) {}
};
const int maxn = 1e5+5;
int n,start,d,pl,pr,ost;
Node tree[4*maxn];
int ql,qr,val;
long long atr[maxn];
long long ans = 0;
Node Merge(Node n1, Node n2)
{
return {n1.br+n2.br , n1.sum+n2.sum};
}
void make_clear(int v, int l, int r)
{
if(l==r)
{
tree[v] = {0,0};
if(r==0) tree[v] = {1,0};
return;
}
int mid = (l+r)/2;
make_clear(v*2+0,l,mid+0);
make_clear(v*2+1,mid+1,r);
tree[v] = Merge(tree[v*2+0],tree[v*2+1]);
}
void pre_clear()
{
ans = 0;
make_clear(1,0,n);
pl = pr = 0;
}
long long query(int v, int l, int r, int ost)
{
if(ost==0) return 0;
if(tree[v].br <= ost) return tree[v].sum;
if(l == r) return (tree[v].sum / tree[v].br) * ost;
int mid = (l+r)/2;
if(tree[v*2+1].br > ost) query(v*2+1,mid+1,r,ost);
return query(v*2+0,l,mid+0,ost-tree[v*2+1].br) + tree[v*2+1].sum;
}
void update(int v, int l, int r)///map
{
if(l==r)
{
if(val==1)
{
tree[v].br++;
tree[v].sum += r;
}
else
{
tree[v].br--;
tree[v].sum -= r;
}
return;
}
int mid = (l+r)/2;
if(qr<=mid) update(v*2+0,l,mid+0);
else update(v*2+1,mid+1,r);
tree[v] = Merge(tree[v*2+0],tree[v*2+1]);
}
void p_activate(int l, int r)
{
while(l<pl)
{
pl--;
val = 1;
ql = qr = atr[pl];///map
update(1,0,n);
}
while(pr<r)
{
pr++;
val = 1;
ql = qr = atr[pr];///map;
update(1,0,n);
}
while(pl<l)
{
val = -1;
ql = qr = atr[pl];///map
update(1,0,n);
pl++;
}
while(r<pr)
{
val = -1;
ql = qr = atr[pr];///map
update(1,0,n);
pr--;
}
}
void divide(int l, int r, int optl, int optr)
{
if(l>r) return;
int mid = (l+r)/2;
pair<long long,int> best = {-1,-1};
for(int i = optl; i <= optr; i++)
{
int ost = d - 2*(mid-start);///mozhe da se optimizira FOR
if(ost<0) continue;
p_activate(i,mid);
long long pom = query(1,0,n,ost);
if(pom>best.first) best = {pom,i};
}
ans = max(ans,best.first);
int opt = best.second;
if(opt == -1) divide(l,mid-1,optl,optr);
else
{
divide(l,mid-1,optl,opt);
divide(mid+1,r,opt,optr);
}
}
long long solve(int sti, int di)
{
start = sti;
d = di;
pre_clear();
divide(start,n-1,0,start);
return ans;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[])
{
n = N;
for(int i = 0; i < n; i++) atr[i] = attraction[i];
long long res = solve(start,d);
reverse(atr+0,atr+n);
res = max(res,solve(n-1-start,d));
return res;
}
