#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll dp[N], opt[N];
int tab[N];
int n, s, d;
multiset<int> S, S2;//S-dobre, S2-reszta
multiset<int> co;
ll sum=0;
void dodaj(int i){
//cout<<"+ "<<i<<"\n";
co.insert(i);
S.insert(tab[i]);
sum+=tab[i];
}
void usun(int i){
//cout<<"- "<<i<<"\n";
co.erase(co.find(i));
if(S.find(tab[i])!=S.end()){
sum-=tab[i];
S.erase(S.find(tab[i]));
}
else S2.erase(S2.find(tab[i]));
}
void out(){
cout<<co.size()<<"\n";
for(int i:co)cout<<i<<" ";
cout<<"\n";
}
int L=0, R=0;
void solve(int l, int r, int lopt, int ropt){
//cout<<l<<" "<<r<<" "<<lopt<<" "<<ropt<<endl;
//out();
if(l>r) return;
int m=(l+r+1)>>1;
while(L>m)dodaj(--L);
while(R<max(m, lopt))dodaj(R++);
while(L<m)usun(L++);
while(R>max(m, lopt))usun(--R);
//cout<<L<<" "<<R<<"\n";
/*for(int i=m; i<=r && i<lopt; i++){
dodaj(i);
}*/
opt[m]=max(lopt, m);
for(int i=opt[m]; i<=ropt; i++){
dodaj(i);
while(S.size()>d+2*m-s-i){
sum-=*S.begin();
S2.insert(*S.begin());
S.erase(S.begin());
}
while(S.size()<d+2*m-s-i && S2.size()){
sum+=*S2.crbegin();
S.insert(*S2.crbegin());
S2.erase(S2.find(*S2.crbegin()));
}
//cout<<m<<" "<<i<<" "<<sum<<"\n";
if(sum>dp[m]){
opt[m]=i;
dp[m]=sum;
}
}
R=ropt+1;
/*for(int i=ropt; i>=opt[m]; i--){
usun(i);
}*/
//cout<<m<<" "<<dp[m]<<" opt: "<<opt[m]<<endl;
//for(int i=lopt; i<m; i++)usun(i);
solve(l, m-1, lopt, opt[m]);
//for(int i=m; i<opt[m] && i<=r; i++)usun(i);
solve(m+1, r, opt[m], ropt);
}
long long int findMaxAttraction(int _n, int start, int _d, int attraction[]) {
n=_n;
d=_d;
s=start;
for(int i=0; i<n; i++)tab[i]=attraction[i];
solve(0, s, 0, n-1);
ll ans=0;
for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
for(int i=0; i<n; i++)tab[i]=attraction[n-1-i];
L=0, R=0;
for(int i=0; i<n; i++)dp[i]=opt[i]=0;
co.clear();
S.clear();
S2.clear();
sum=0;
s=n-1-s;
solve(0, s, 0, n-1);
for(int i=0; i<=s; i++)ans=max(ans, dp[i]);
return ans;
}
