#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define fi first
#define se second
#define pii pair<ll,ll>
#define all(n) (n).begin(),(n).end()
#define pb push_back
#define dbg(x) cerr<<#x<<" = "<<x<<'\n';
struct Persistent_tree{
int l, r;
ll tot, cnt;
}tr[16000005];
int idx = 0, rt[400005];
void insert(int copy, int &now, int pos, int val, int L, int R){
now = ++idx;
tr[now] = tr[copy];
tr[now].cnt++;
tr[now].tot += val;
if(L == R) return;
int M = (L+R) / 2;
if(val <= M) insert(tr[copy].l, tr[now].l, pos, val, L, M);
else insert(tr[copy].r, tr[now].r, pos, val, M+1, R);
}
ll query(int L ,int R ,int lid, int rid, int num){
/* dbg(lid); */
/* dbg(rid); */
/* dbg(num); */
/* cout<<L<<" "<<R<<" "<<tr[rid].cnt - tr[lid].cnt<<" "<<tr[rid].tot - tr[lid].tot<<" "<<num<<'\n'; */
if(tr[rid].cnt - tr[lid].cnt <= num) return tr[rid].tot - tr[lid].tot;
if(!num) return 0;
ll M = (L+R)/2;
int Rr = tr[rid].r, Rl = tr[rid].l, Lr = tr[lid].r, Ll = tr[lid].l;
if(tr[Rr].cnt - tr[Lr].cnt <= num){
num -= tr[Rr].cnt - tr[Lr].cnt;
return tr[Rr].tot - tr[Lr].tot + query(L,M,Ll, Rl, num);
}
else return query(M+1,R,Lr, Rr, num);
}
ll solve(int n, int s, int d, int arr[]){
ll ans = 0;
if(s != 1){
for(int i=0;i<idx;i++) tr[i].l = tr[i].r = tr[i].tot = tr[i].cnt = 0;
idx = 1;
rt[0] = 1;
}
for(int i=1;i<=n;i++){
insert(rt[i-1], rt[i], i, arr[i], 0, 1000000000);
}
while(1){
cout<<'\n';
}
for(int i=1;i<=s;i++){
if(d < s-i) continue;
ll tans = query(0,1000000000, rt[i-1], rt[s], d - (s-i));
/* dbg(tans); */
for(int j=s+1;j<=n;j++){
ll left = d - (s-i) - (j-i);
if(left <= 0) break;
ll que = query(0,1000000000, rt[i-1], rt[j], left);
/* cout<<"It's "<< i <<" and "<<j<<" left is "<<left<<'\n'; */
/* cout<<"Ans is "<<que<<'\n'; */
tans = max(tans, que);
}
ans = max(ans, tans);
}
return ans;
}
int arr[200005];
ll findMaxAttraction(int n, int start, int d, int in[]) {
start++;
for(int i=1;i<=n;i++) arr[i] = in[i-1];
if(start == 1){
return solve(n, 1, d, arr);
}
ll al = solve(n, start, d, arr);
for(int i=0;i<n/2;i++) swap(arr[i], arr[n-i]);
start = n - start;
ll ar = solve(n, start, d, arr);
return max(al, ar);
}
