#include"holiday.h"
#include<algorithm>
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
struct node{
int cnt;
long long sum;
node(){cnt=0,sum=0;}
};
struct SegTree{
int N;
vector<node>tree;
node merge(node a,node b){
a.sum+=b.sum;
a.cnt+=b.cnt;
return a;
}
SegTree(int n){
N=1;
while(N<n){N<<=1;}
tree.assign(2*N,node());
}
void update(int v,int l,int r,int id,int x){
if(r-l==1){
tree[v].sum+=x;
tree[v].cnt++;
return;
}
int mid=(l+r)/2;
if(id<mid) update(v<<1,l,mid,id,x);
else update(v<<1|1,mid,r,id,x);
tree[v]=merge(tree[v<<1],tree[v<<1|1]);
}
void update(int id,int x){
return update(1,0,N,id,x);
}
node get(int v,int l,int r,int ql,int qr){
if(l>=qr || ql>=r) return node();
if(l>=ql && qr>=r) return tree[v];
int mid=(l+r)/2;
return merge(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid,r,ql,qr));
}
node get(int l,int r){
return get(1,0,N,l,r);
}
};
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
if(d==0) return 0LL;
ll ans=0;
vector<int>comp;
for(int i=0;i<n;i++) comp.push_back(attraction[i]);
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
int m=comp.size();
for(int l=max(0,start-d+1);l<=start;l++){
SegTree S(m);
for(int r=l;r<n;r++){
S.update(lower_bound(comp.begin(),comp.end(),attraction[r])-comp.begin(),attraction[r]);
int k=(r-start)+(start-l)+min(r-start,start-l);
if(k>=d) break;
int c=d-k;
if(r>=start){
int lo=0,hi=m;
while(hi-lo>1){
int mid=(hi+lo)/2;
if(S.get(mid,m).cnt>=c) lo=mid;
else hi=mid;
}
node a=S.get(lo,m);
// cout<<a.cnt<<'\n';
a.sum-=1LL*max(0,a.cnt-c)*comp[lo];
ans=max(ans,a.sum);
}
}
}
return ans;
}
