#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int dpf[N], dpg[N], n, st, A[N], POS[N], num[N];
ll valf[N], valg[N], T[N];
int ptr;
vector<pii> val;
void build(int sz){
for(int j = 0; j <= 4*sz; ++j) num[j]=T[j]=0;
}
void upd(int l, int r, int p, int k, bool f){
if(l == r){
if(f)
num[k] = 1, T[k] = val[l].ff;
else
num[k] = 0, T[k] = 0;
return;
}
int m = l+r>>1;
if(p <= m) upd(l, m, p, k<<1, f);
else upd(m+1, r, p, k<<1|1, f);
num[k] = num[k<<1] + num[k<<1|1];
T[k] = T[k<<1] + T[k<<1|1];
}
ll get(int l, int r, int tot, int k){
if(num[k] == 0 || tot == 0) return 0ll;
int m = l + r >> 1;
if(tot >= num[k]){
return T[k];
}
if(l==r) return 0ll;
if(num[k<<1|1] <= tot){
return get(l, m, tot - num[k<<1|1], k<<1) + T[k<<1|1];
}
return get(m+1, r, tot, k<<1|1);
}
void calcf(int pos, int ql, int qr){
dpf[pos] = ql;
// cout << ptr << "f\n";
for(; ptr < ql; ++ptr){
upd(0, n-1, POS[ptr], 1, 1);
}
for(; ptr > ql; --ptr){
upd(0, n-1, POS[ptr-1], 1, 0);
}
ll best = 0;
for(; ptr <= qr; ++ptr){
if(pos - (ptr - st) < 0) break;
upd(0, n-1, POS[ptr], 1, 1);
ll f = get(0, n-1, pos - (ptr - st), 1); //cout << num[1] << ' ' << ptr << ' ' << f << ' ' << POS[ptr] << ' ' << pos - ptr + st << '\n';
if(f > best) best = f, dpf[pos] = ptr;
}
valf[pos] = best;
}
void calcg(int pos, int ql, int qr){
dpg[pos] = qr;
for(; ptr > qr; --ptr){
upd(0, n-1, POS[ptr], 1, 1);
}
for(; ptr < qr; ++ptr){
upd(0, n-1, POS[ptr+1], 1, 0);
}
ll best = 0;
for(; ptr >= ql; --ptr){
if(pos - (st - ptr) < 0) break;
upd(0, n-1, POS[ptr], 1, 1);
ll f = get(0, n-1, pos - (st - ptr), 1);
if(f > best) best = f, dpg[pos] = ptr;
}
valg[pos] = best;
}
void f(int l, int r, int ql, int qr){
if(r < l) return;
int mid = l+r>>1;
calcf(mid, ql, qr);
if(l == r) return;
f(l, mid - 1, ql, dpf[mid]);
f(mid + 1, r, dpf[mid], qr);
}
void g(int l, int r, int ql, int qr){
if(r < l) return;
int mid = l+r>>1;
calcg(mid, ql, qr);
if(l == r) return;
g(l, mid - 1, dpg[mid], qr);
g(mid + 1, r, ql, dpg[mid]);
}
long long int findMaxAttraction(int nn, int start, int d, int AA[]) {
st = start;
n = nn;
for(int i = 1; i <= n; ++i){
A[i-1]=AA[i-1];
val.pb({A[i-1],i-1});
}
sort(all(val));
for(int i = 1; i <= n; ++i){
POS[val[i-1].ss] = i - 1;
}
build(n);
ptr = start;
f(0, d, start, n - 1);
if(start == 0){
return valf[d];
}
build(n);
ptr = start - 1;
g(1, d, 0, start - 1);
ll ans = 0;
for(int i = 0; i <= d; ++i){
int go = dpf[i];
if(d - i - (go - start) > 0)
ans = max(ans, valf[i] + valg[d - i - (go - start)]);
ans = max(ans, valf[i]);
// cout << i << ' ' << valf[i] << '\n';
}
for(int i = 1; i <= d; ++i){
int go = dpg[i];
if(d - i - (start - go) > 0)
ans = max(ans, valg[i] + valf[d - i - (start - go)]);
ans = max(ans, valg[i]);
if(i < d) ans = max(ans, valg[i] + A[start]);
}
return ans;
}
