#include <bits/stdc++.h>
using namespace std;
#include "holiday.h"
struct range_sum {
int l,r,s,m; long long res; vector<int>& A; multiset<int,greater<int>> B,C;
long long mv(){
int d = max(0,m-(s-l)-(r-l));
while(!C.empty()&&B.size()<d) res += *C.begin(),B.emplace(*C.begin()),C.erase(C.begin());
while(B.size()>d) res -= *B.rbegin(),C.emplace(*B.rbegin()),B.erase(prev(B.end()));
while(!B.empty()&&!C.empty()&&*B.rbegin()<*C.begin()){
res += *C.begin(),B.emplace(*C.begin()),C.erase(C.begin());
res -= *B.rbegin(),C.emplace(*B.rbegin()),B.erase(prev(B.end()));
}
return res;
}
range_sum(vector<int>& D,int t,int d) : l(0),r(0),s(t),m(d),res(0),A(D),B(),C() {
C.emplace(A[0]),mv();
}
long long increase_right(){
C.emplace(A[++r]);
return mv();
}
long long decrease_left(){
C.emplace(A[--l]);
return mv();
}
long long del(int x){
if (!B.empty()&&*B.rbegin()<=x) res -= x,B.erase(B.find(x));
else C.erase(C.find(x));
return mv();
}
long long decrease_right(){
return del(A[r--]);
}
long long increase_left(){
return del(A[l++]);
}
long long set(int x,int y){
while(r<y) increase_right();
while(l>x) decrease_left();
while(r>y) decrease_right();
while(l<x) increase_left();
return res;
}
};
long long findMaxAttraction(int n,int start,int m,int AA[]){
vector<int> A(AA,AA+n);
auto dp = [&](auto& dp,range_sum& B,int a,int b,int c,int d) -> long long {
int mid = (a+c)/2;
long long res(0); int ind(b);
for (int i(b);i <= d;++i) if (res<B.set(mid,i)) res = B.res,ind = i;
long long ret = res;
if (a<mid) ret = max(ret,dp(dp,B,a,b,mid-1,ind));
if (mid<c) ret = max(ret,dp(dp,B,mid+1,ind,c,d));
return ret;
};
auto solve = [&]() -> long long {
range_sum B(A,start,m);
return dp(dp,B,0,start,start,n-1);
};
long long res = solve();
reverse(A.begin(),A.end()),start = n-start-1;
return max(res,solve());
}
