#include"holiday.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
struct PST{
struct no{
int lch=-1,rch=-1;
int val=0;
long long v2=0;
};
vector<no> st;
int nw=1;
void build(int v,int L,int R){
if(L==R){
return;
}
st[v].lch=nw;
nw++;
st[v].rch=nw;
nw++;
int m=(L+R)/2;
build(st[v].lch,L,m);
build(st[v].rch,m+1,R);
}
void update(int L,int R,int fr,int &to,int p,int t,int t2){
to=nw;
st[nw]=st[fr];
st[nw].val+=t;
st[nw].v2+=t2;
nw++;
if(L==R){
return;
}
int m=(L+R)/2;
if(p<=m){
update(L,m,st[fr].lch,st[to].lch,p,t,t2);
}
else{
update(m+1,R,st[fr].rch,st[to].rch,p,t,t2);
}
}
long long query(int L,int R,int fr,int to,int k){
if(L==R){
return st[to].v2-st[fr].v2;
}
int sum=st[st[to].rch].val-st[st[fr].rch].val;
int m=(L+R)/2;
if(sum>=k){
return query(m+1,R,st[fr].rch,st[to].rch,k);
}
else{
return query(L,m,st[fr].lch,st[to].lch,k-sum)+st[st[to].rch].v2-st[st[fr].rch].v2;
}
}
vector<int> root;
int n;
void init(vector<int> a){
st.resize(1000000);
n=a.size();
vector<pair<int,int> > z(n);
for(int i=0;i<n;i++){
z[i]={a[i],i};
}
sort(z.begin(),z.end());
for(int i=0;i<n;i++){
a[i]=lower_bound(z.begin(),z.end(),pair<int,int>(a[i],i))-z.begin();
}
root.resize(n+1);
root[0]=0;
build(0,0,n-1);
for(int i=1;i<=n;i++){
update(0,n-1,root[i-1],root[i],a[i-1],1,z[a[i-1]].fs);
}
}
long long ask(int l,int r,int k){
if(k<=0){
return 0;
}
k=min(k,r-l+1);
long long u=query(0,n-1,root[l],root[r+1],k);
return u;
}
}pst[2];
int n,st,k;
long long ans=0;
void dc(int l,int r,int u,int d,int c){
if(l>r || u>d){
return;
}
pair<long long,int> p(0,0);
int m=(l+r)/2;
for(int i=u;i<=d;i++){
p=max(p,{pst[c].ask(st-2*m,st+i,k-2*m-i),i});
}
ans=max(ans,p.fs);
dc(l,m-1,u,p.sc,c);
dc(m+1,r,p.sc,d,c);
}
void solve(vector<int> v,int c){
pst[c].init(v);
//dp[i][j]=pst.ask(st-2*i,st+j,d-2*i-j);
int a=st,b=n-st-1;
for(int i=0;i<=a;i++){
for(int j=0;j<=b;j++){
if(2*i<=j){
ans=max(ans,pst[c].ask(st-i,st+j,k-2*i-j));
}
}
}
//dc(0,a,0,b,c);
}
long long findMaxAttraction(int _n, int _st, int _k, int at[]) {
n=_n;
k=_k;
st=_st;
vector<int> v(n);
for(int i=0;i<n;i++){
v[i]=at[i];
}
solve(v,0);
st=_n-_st-1;
reverse(v.begin(),v.end());
solve(v,1);
return ans;
}
