#include <bits/stdc++.h>
#define N 100005
#include"holiday.h"
using namespace std;
struct BIT{
vector<long long> bit;
int n;
BIT(int size){
n = size;
bit.assign(n,0);
}
void upd(int pos,int val){
for(;pos < n;pos += pos & -pos){
bit[pos] += val;
}
}
long long get(int pos){
long long ret = 0;
for(;pos > 0;pos -= pos & -pos){
ret += bit[pos];
}
return ret;
}
int get_kth(int k){
int ret = 0;
for(int i = 20;i>=0;i--){
if((1<<i) + ret < n && bit[ret + (1<<i)] < k){
k -= bit[ret + (1<<i)];
ret += (1<<i);
}
}
return ret+1;
}
};
int rel[N];
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
long long ans = 0;
vector<int> compress;
for(int i = 0;i<n;i++){
compress.push_back(-attraction[i]);
}
sort(compress.begin(),compress.end());
compress.resize(unique(compress.begin(),compress.end())-compress.begin());
for(int i = 0;i<compress.size();i++){
rel[i+1] = -compress[i];
}
for(int i = 0;i<n;i++){
attraction[i] = lower_bound(compress.begin(),compress.end(),-attraction[i])-compress.begin() + 1;
}
vector<pair<pair<int,int>,pair<int,int>>> q;
q.push_back({{0,start},{start,n-1}});
while(q.size()){
vector<pair<pair<int,int>,pair<int,int>>> nw;
BIT bt1(n);
BIT bt2(n);
int l = 0,r = -1;
for(auto u:q){
//cout << u.first.first << " " << u.first.second << endl;
//cout << u.second.first << " " << u.second.second << endl;
if(u.first.first > u.first.second)continue;
int m = (u.first.first + u.first.second)/2;
while(l < m){
bt1.upd(attraction[l],-1);
bt2.upd(attraction[l],-rel[attraction[l]]);
l++;
}
int opt = u.second.first;
long long maxi = 0;
for(int i = u.second.first;i<=u.second.second;i++){
while(r < i){
r++;
bt1.upd(attraction[r],1);
bt2.upd(attraction[r],rel[attraction[r]]);
}
//cout << l << " " << m << " " << r << " " << i << endl;
int cost = 0;
if(m == start || i == start)cost = abs(m-start)+abs(i-start);
else cost = abs(m-i)+min(abs(m-start),abs(i-start));
int left = min(i-m+1,d - cost);
if(left <= 0)continue;
int pos = bt1.get_kth(left) -1;
long long nowans = bt2.get(pos) + (left - bt1.get(pos)) * (rel[pos+1]);
//cout << cost << " " << left << " " << nowans << endl;
if(nowans > maxi){
maxi = nowans;
opt = i;
}
ans = max(ans,nowans);
}
//cout << opt << endl;
nw.push_back({{u.first.first,m-1},{u.second.first,opt}});
nw.push_back({{m+1,u.first.second},{opt,u.second.second}});
}
q = nw;
}
return ans;
}
