#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 300010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N,D,S,A[maxn];
int disc[maxn], undisc[maxn];
int F[maxn],G[maxn];
struct node{
int s,e,m,val=0,num=0;
node *l,*r;
node(int ss,int ee){
s = ss; e = ee; m = (s + e) / 2;
if (s != e){
l = new node(s,m); r = new node(m+1,e);
}
}
void upd(int p,int v){
if (s == e){
val += undisc[s] * v; num += v;
}else{
if (p > m) r->upd(p, v);
else l->upd(p,v);
val = l->val + r->val;
num = l->num + r->num;
}
}
int qry(int v){
if (s == e) return (v > 0) * val;
if (r->num < v) return r->val + l->qry(v-r->num);
else return r->qry(v);
}
void clear(){
val = num = 0;
if (s != e){
l->clear(); r->clear();
}
}
}*root;
int Fval[maxn], Gval[maxn];
void dnc(int l,int r,int vl,int vr){
// root is at vl-1
if (l > r) return;
int m = (l + r) / 2;
F[m] = vl; int cur = -1;
FOR(i,vl,vr){ // s to i
root->upd(disc[i], 1);
int val = root->qry(m - (i - S));
if (val > cur){
cur = val; F[m] = i;
}
}
//cout << m << ' ' << cur << '\n';
Fval[m] = cur;
FOR(i,F[m],vr) root->upd(disc[i], -1);
dnc(m+1,r,F[m],vr);
FOR(i,vl,F[m]-1) root->upd(disc[i], -1);
dnc(l,m-1,vl,F[m]);
}
void backdnc(int l,int r,int vl,int vr){
// root is at vr+1
if (l > r) return;
int m = (l + r) / 2;
G[m] = vr; int cur = -1;
DEC(i,vr,vl){ // i to s
root->upd(disc[i], 1);
int val = root->qry(m - (S-1 - i));
if (val > cur){
cur = val; G[m] = i;
}
}
//cout << m << ' ' << Gval[m] << ' ' << cur << '\n';
Gval[m] = cur;
FOR(i,vl,G[m]) root->upd(disc[i], -1);
backdnc(m+1,r,vl,G[m]);
FOR(i,G[m]+1,vr) root->upd(disc[i], -1);
backdnc(l,m-1,G[m],vr);
}
int solve(){
root->clear();
dnc(0, D, S, N-1);
root->clear();
backdnc(0,D,0,S-1);
int ans = max(Fval[D], Gval[D]);
FOR(i,1,D){ // number of days spent going right
if (D - (i + (F[i] - S)) - 1 >= 0){
ans = max(ans, Gval[D - (i + (F[i] - S))-1] + Fval[i]);
//cout << i << ' ' << ans << '\n';
}
}
FOR(i,1,D){ // number of days spent going left
if (D - (i + (S - 1 - G[i])) - 2 >= 0) ans = max(ans, Fval[D - (i + (S - 1 - G[i])) - 2] + Gval[i]);
}
//FOR(i,0,D) cout << G[i] << ' ';
return ans;
}
ll findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
N = n; D = d; S = start;
root = new node(0,N-1);
vpi v;
FOR(i,0,N-1){
A[i] = attraction[i];
v.pb(pi(A[i], i));
}
sort(all(v));
FOR(i,0,N-1){
disc[v[i].s] = i;
undisc[i] = v[i].f;
}
return solve();
}
