#include"holiday.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(Int i = (Int)(a); i < (Int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
const Int INF = 1e18;
const Int N = 2e5+5;
const Int LN = 20;
Int sz;
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
#define mid (tl+tr)/2
struct Segtree{
Int sum[2*N], cnt[2*N];
void reset(){
rep(v,0,2*N) sum[v] = cnt[v] = 0;
}
void upd(Int i,Int x,Int v=0,Int tl=0,Int tr=sz-1){
// if(v==0) cout << i _ x << nl;
if(tl==tr){
sum[v] = x; cnt[v] = 1; return;
}
if(i<=mid) upd(i,x, lc,tl,mid);
else upd(i,x, rc,mid+1,tr);
sum[v] = sum[lc] + sum[rc];
cnt[v] = cnt[lc] + cnt[rc];
}
// query sum of largest k values
Int qry(Int k,Int v=0,Int tl=0,Int tr=sz-1){
if(k <= 0) return 0;
if(cnt[v] <= k) return sum[v];
Int kr = min(k, cnt[rc]);
return qry(k-kr, lc,tl,mid) + qry(kr, rc,mid+1,tr);
}
} segtree;
#undef mid
// what to check at index i
V<Int> chk[N];
// parent interval
Int chkl[N], chkr[N];
Int lastl[N], lastr[N];
V<Int> solve(V<Int> a){
sz = (Int)a.size();
V<Int> ret(2*sz,0), last(2*sz,0);
// sort and find its order
V<Int> ord(sz);
rep(i,0,sz) ord[i] = i;
sort(all(ord),[&](Int i,Int j){
return a[i] < a[j];
});
V<Int> iord(sz);
rep(i,0,sz){
iord[ord[i]] = i;
}
// for(Int i : iord) cout << i << " ";
// cout << nl;
Int t = 1;
chkl[sz] = 0; chkr[sz] = 2*sz-1;
lastl[sz] = 0; lastr[sz] = sz-1;
rep(i,lastl[sz],lastr[sz]+1) chk[i].push_back(sz);
while(1){
segtree.reset();
V<Int> solved;
rep(i,0,sz){
segtree.upd(iord[i],a[i]);
while(!chk[i].empty()){
Int j = chk[i].back(); chk[i].pop_back();
// dbg(j);
// dbg(solved.size());
// if(!solved.empty()) dbg(solved[0]);
if(solved.empty() || solved.back()!=j){
// cout << "INS" _ j << nl;
solved.push_back(j);
}
Int x = segtree.qry(j-i);
if(x > ret[j]){
ret[j] = x; last[j] = i;
}
}
}
// dbg(segtree.qry(3));
// break;
bool cont = 0;
for(Int j : solved){
// dbg(j);
// cout << chkl[j] _ chkr[j] << nl;
cont |= chkl[j] != chkr[j];
if(chkl[j] < j){
Int m = (chkl[j] + j-1)/2;
// dbg(m);
chkl[m] = chkl[j]; chkr[m] = j-1;
lastl[m] = lastl[j]; lastr[m] = last[j];
rep(i,lastl[m],lastr[m]+1){
// cout << "INS" _ m << nl;
chk[i].push_back(m);
}
}
if(j < chkr[j]){
Int m = (j+1 + chkr[j])/2;
// dbg(m);
chkl[m] = j+1; chkr[m] = chkr[j];
lastl[m] = last[j]; lastr[m] = lastr[j];
rep(i,lastl[m],lastr[m]+1){
chk[i].push_back(m);
}
}
}
if(!cont) break;
}
// Int prv = 0;
// for(Int x : ret){
// assert(prv <= x);
// prv = x;
// }
return ret;
}
Int findMaxAttraction(int n,int s,int d,int a[]){
Int ans = 0;
// V<Int> v = {20,0,2,0,10};
// for(Int x : v) cout << x << " ";
// cout << nl;
// for(Int x : solve(v)) cout << x << " ";
// cout << nl;
// return ans;
rep(loop,0,2){
V<Int> l, r;
l = {0};
for(Int i=s-1; i>=0; i--){
l.push_back(a[i]);
}
r = {a[s]};
for(Int i=s+1; i<n; i++){
r.push_back(0);
r.push_back(a[i]);
}
V<Int> vl = solve(l);
// dbg(l.size());
// for(Int x : l) cout << x << " ";
// cout << nl;
// dbg(vl.size());
// for(Int x : vl) cout << x << " ";
// cout << nl << nl;
V<Int> vr = solve(r);
// dbg(r.size());
// for(Int x : r) cout << x << " ";
// cout << nl;
// dbg(vr.size());
// for(Int x : vr) cout << x << " ";
// cout << nl << nl;
// go right, then left
for(Int dl=0,dr=d; dr>=0; dl++,dr--){
Int ansl = dl<(Int)vl.size() ? vl[dl] : vl.back();
Int ansr = dr<(Int)vr.size() ? vr[dr] : vr.back();
ans = max(ans, ansl+ansr);
}
// dbg(ans);
// reverse all
reverse(a,a+n);
s = n-1-s;
// cout << nl << nl;
}
return ans;
}
