#include"holiday.h"
#include <bits/stdc++.h>
#define N 300005
using namespace std;
struct BIT{
vector<pair<int,long long>> bit;
int n;
BIT(int sz){
n = sz + 5;
bit.assign(n,{0,0});
}
void upd(int pos,int val1,int val2){
for(;pos < n;pos += pos & - pos){
bit[pos].first += val1;
bit[pos].second += val2;
}
}
long long get(int k){
long long ret = 0;
int pos = 0;
for(int i = 20;i>=0;i--){
if((pos + (1<<i )) >= n)continue;
if(bit[pos + (1<<i)].first <= k){
ret += bit[pos + (1<<i)].second;
k -= bit[pos + (1<<i)].first;
pos += (1<<i);
}
}
return ret;
}
}bt(N);
int val[N];
int ord[N];
long long ans[N];
int cur = 0;
void solve(int l,int r,int optl,int optr,int x){
if(r < l)
return;
while(cur < optl){
cur++;
bt.upd(ord[cur],1,val[ord[cur]]);
}
while(cur > optl){
bt.upd(ord[cur],-1,-val[ord[cur]]);
cur--;
}
int m = (l + r)/2;
int opt = -1;
ans[m] = -1;
int now = (optl) * x;
for(int i = optl;i <= optr;i++){
if(now > m)break;
long long tmp = bt.get(m - now);
if(tmp > ans[m]){
ans[m] = tmp;
opt = i;
}
now += x;
if(i != optr){
cur++;
bt.upd(ord[cur],1,val[ord[cur]]);
}
}
solve(l,m-1,optl,opt,x);
solve(m+1,r,opt,optr,x);
}
vector<long long> get(int d,int x,vector<int> a){
int n = a.size();
for(int i = 0;i<n;i++){
ord[i + 1] = a[i];
}
solve(0,d,0,n,x);
while(cur > 0){
bt.upd(ord[cur],-1,-val[ord[cur]]);
cur--;
}
vector<long long> ret;
for(int i = 0;i<=d;i++){
ret.push_back(ans[i]);
}
return ret;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
long long ans = 0;
vector<int> tmp;
for(int i = 0;i<n;i++){
tmp.push_back(i);
}
sort(tmp.begin(),tmp.end(),[&](int a,int b){
return attraction[a] > attraction[b];
});
vector<int> ord(n);
for(int i = 0;i<n;i++){
ord[tmp[i]] = i + 1;
val[i + 1] = attraction[tmp[i]];
}
vector<int> l,r;
for(int i = start-1;i>=0;i--){
l.push_back(ord[i]);
}
for(int i = start + 1;i<n;i++){
r.push_back(ord[i]);
}
auto l1 = get(d,1,l);
auto l2 = get(d,2,l);
auto r1 = get(d,1,r);
auto r2 = get(d,2,r);
ans = max(ans,l1[d]);
ans = max(ans,r1[d]);
// cout << ans << endl;
// for(auto u:l1){
// cout << u << ' ';
// }
// cout << endl;
// for(auto u:l2){
// cout << u << ' ';
// }
// cout << endl;
// for(auto u:r1){
// cout << u << ' ';
// }
// cout << endl;
// for(auto u:r2){
// cout << u << ' ';
// }
// cout << endl;
for(int xx = 0;xx < 2;xx++){
d -= xx;
int add = 0;
if(xx)
add = attraction[start];
for(int i = 0;i<=d;i++){
ans = max(ans,l1[d-i] + r2[i] + add);
// cout << i << ' ' << ans << endl;
ans = max(ans,r1[d-i] + l2[i] + add);
// cout << i << ' ' << ans << endl;
}
}
return ans;
}
