#include<bits/stdc++.h>
#define newl '\n'
#include<holiday.h>
const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;
struct Node{
Node *l,*r;
long long val,cnt;
Node(long long val,long long cnt) : l(nullptr),r(nullptr),val(val),cnt(cnt){
}
Node(Node *ll,Node *rr){
assert(ll && rr);
l = ll;
r = rr;
val = l->val + r->val;
cnt = l->cnt + r->cnt;
}
};
typedef Node* pNode;
struct PersistentST{
std::vector<pNode> root;
PersistentST(){
root.emplace_back(new Node(0LL,0LL));
root.back()->l = root.back();
root.back()->r = root.back();
}
pNode update(int l,int r,int pos,int val,pNode t){
if(l == r){
return new Node(val,1);
}
int mid = (l + r) / 2;
if(pos <= mid){
return new Node(update(l,mid,pos,val,t->l),t->r);
}
return new Node(t->l,update(mid + 1,r,pos,val,t->r));
}
long long query(int l,int r,int val,pNode t){
if(l == r){
return t->val;
}
int mid = (l + r) / 2;
if(val <= t->l->cnt){
return query(l,mid,val,t->l);
}
return t->l->val + query(mid + 1,r,val - t->l->cnt,t->r);
}
public:
long long query(int l,int r,int pos,int ver){
return query(l,r,pos,root[ver]);
}
void update(int l,int r,int pos,int val,int ver){
root.emplace_back(update(l,r,pos,val,root[ver]));
}
};
std::vector<long long> optimal(const std::vector<int> &a){
int n = (int)a.size() - 1;
std::vector<int> id(n + 1,0);
std::vector<long long> ans(1,0);
auto compress = [&](){
std::map<int,int> m;
for(int i = 1;i <= n;++i){
++m[a[i]];
}
std::map<int,int>::iterator it;
for(it = m.end();it != m.begin();it = prev(it)){
if(it != m.end() && next(it) != m.end()){
it->second += next(it)->second;
}
}
if((int)m.size() > 1){
it->second += next(it)->second;
}
for(int i = n;i >= 1;--i){
// std::cout << "IMP " << i << " " << m[a[i]] << newl;
id[i] = m[a[i]]--;
}
};
compress();
std::set<int> s;
std::map<int,int> m;
PersistentST st;
auto eval = [&](int ver,int opt) -> long long{
if(ver > opt){
return -INF;
}
return st.query(1,n,opt - (ver - 1),ver);
};
auto get = [&](int opt) -> long long{
// assert(!s.empty());
int x = *prev(s.upper_bound(opt));
int ver = m[x];
assert(opt >= ver);
return eval(ver,opt);
};
auto dominate = [&](int cur) -> void{
while(!s.empty()){
int x = *s.rbegin();
// std::cerr << eval(m[x],x) << " " << eval(cur,x) << newl;
if(eval(m[x],x) <= eval(cur,x)){
s.erase(x);
m.erase(x);
}else{
break;
}
}
if(s.empty()){
s.insert(1);
m[1] = cur;
return;
}
int prev = m[*s.rbegin()];
int lo = *s.rbegin() + 1,hi = n * 2,ans = n * 2;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(eval(prev,mid) < eval(cur,mid)){
hi = mid - 1;
ans = mid;
}else{
lo = mid + 1;
}
}
s.insert(ans);
m[ans] = cur;
// auto dfs = [&](auto dfs, int u, int p) -> void{
// for(int v : adj[u]){
// if(v == p) continue;
// dfs(dfs, v, u);
// }
// }
};
for(int i = 1;i <= n;++i){
st.update(1,n,id[i],a[i],i - 1);
dominate(i);
}
// return ans;
for(int i = 1;i <= n * 2;++i){
ans.emplace_back(get(i));
// std::cout << ans.back() << " ";
}
// std::cout << newl;
return ans;
}
long long solve(const std::vector<int> &a,int s,int k){
int n = (int)a.size() - 1;
long long ans = 0;
// return 0;
std::vector<int> left(2,0),right(1,0);
for(int i = s;i <= n;++i){
right.emplace_back(a[i]);
}
for(int i = s - 1;i >= 1;--i){
left.emplace_back(0);
left.emplace_back(a[i]);
}
// std::cerr << "LEFT\n";
std::vector<long long> f = optimal(left);
// std::cerr << "RIGHT\n";
std::vector<long long> f1 = optimal(right);
// return 0;
for(int i = 0;i < std::min((int)f1.size(),k + 1);++i){
int it = std::max(0,std::min((int)f.size() - 1,k - i));
ans = std::max(ans,f[it] + f1[i]);
}
return ans;
}
long long int findMaxAttraction(int n,int start,int d,int attraction[]){
long long ans = 0;
++start;
std::vector<int> a(n + 1,0);
for(int i = 1;i <= n;++i){
a[i] = attraction[i - 1];
}
ans = std::max(ans,solve(a,start,d));
std::reverse(a.begin() + 1,a.end());
start = n - start + 1;
ans = std::max(ans,solve(a,start,d));
return ans;
}
//int main(){
// std::ios_base::sync_with_stdio(false);
// std::cin.tie(nullptr);std::cout.tie(nullptr);
//
// return 0;
//}
