#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int CT = 200;
const int INF = 1e9;
int n,start,d;
int a[100005];
struct config
{
int le,ri;
set<pair<int,int>> luate,neluate;
ll sum_luate;
bool good()
{
if(2*(ri-start) + (start-le) + (int)luate.size() <= d)
return 1;
assert(luate.empty());
return 0;
}
void increase_le()
{
if(luate.find({a[le],le})!=luate.end())
{
luate.erase({a[le],le});
sum_luate -= a[le];
}
else
neluate.erase({a[le],le});
le++;
balance();
assert(le<=start);
assert(ri>=start);
}
void decrease_le()
{
le--;
baga(le);
balance();
assert(le<=start);
assert(ri>=start);
}
void increase_ri()
{
ri++;
baga(ri);
balance();
assert(le<=start);
assert(ri>=start);
}
void baga(int x)
{
if(!luate.empty() && a[x] > (*luate.begin()).first)
{
sum_luate -= (*luate.begin()).first;
neluate.insert(*luate.begin());
luate.erase(luate.begin());
luate.insert({a[x],x});
sum_luate += a[x];
}
else
neluate.insert({a[x],x});
}
void balance()
{
while(!luate.empty() && 2*(ri-start) + (start-le) + (int)luate.size() > d)
{
sum_luate -= (*luate.begin()).first;
neluate.insert(*luate.begin());
luate.erase(luate.begin());
}
while(!neluate.empty() && 2*(ri-start) + (start-le) + (int)luate.size() + 1 <= d)
{
sum_luate += (*prev(neluate.end())).first;
luate.insert(*prev(neluate.end()));
neluate.erase(prev(neluate.end()));
}
}
void init(int init_le, int init_ri)
{
le = init_le;
ri = init_ri;
assert(le<=start);
assert(ri>=start);
vector<pair<int,int>> v;
for(int i=le;i<=ri;i++)
v.push_back({a[i],i});
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
luate.clear();
neluate.clear();
sum_luate=0;
int ramase = d - 2*(ri-start) - (start-le);
for(int i=0;i<min((int)v.size(),ramase);i++)
{
sum_luate += v[i].first;
luate.insert(v[i]);
}
for(int i=max(0,ramase);i<v.size();i++)
neluate.insert(v[i]);
}
};
ll solve()
{
ll mxm=0;
/*for(int le=start;le>0;le--)
{
config c;
c.init(le,start);
for(int ri=start;ri<=n;ri++)
{
if(c.good()) mxm = max(mxm, c.sum_luate);
if(ri<n) c.increase_ri();
}
}*/
config c;
c.init(1,start);
for(int ri=start;ri<=n;ri++)
{
if(ri!=start) c.increase_ri();
while(c.le+1<=start)
{
ll aux=c.sum_luate, unde=c.le, init_unde=c.le;
int cati = min(CT,start-c.le);
for(int pas=1;pas<=cati;pas++)
{
c.increase_le();
ll x = c.sum_luate;
if(x >= aux)
{
aux = x;
unde = c.le;
}
}
while(c.le > unde)
c.decrease_le();
if(unde==init_unde)
break;
}
//c.init(c.le,c.ri);
if(c.good()) mxm = max(mxm, c.sum_luate);
}
return mxm;
}
ll findMaxAttraction(int cit_n, int cit_start, int cit_d, int cit_a[])
{
n = cit_n;
start = cit_start + 1;
d = cit_d;
for(int i=0;i<n;i++)
a[i+1] = cit_a[i];
ll idk = solve();
reverse(a+1,a+1+n);
start = n - start + 1;
idk = max(idk, solve());
return idk;
}
