#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9;
int n,start,d;
int a[100005];
ll calc(int le, int 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());
ll sum=0;
int ramase = d - 2*(ri-start) - (start-le);
//ramase = min(ramase, (int)v.size());
int mnm=INF;
for(int i=0;i<v.size();i++)
{
mnm = min(mnm, v[i].second);
if(d - 2*(ri-start) - (start-mnm) < i+1)
break;
sum += v[i].first;
}
return sum;
}
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++;
assert(le<=start);
assert(ri>=start);
}
void increase_ri()
{
ri++;
if(!luate.empty() && a[ri] >= (*luate.begin()).first)
{
sum_luate -= (*luate.begin()).first;
neluate.insert(*luate.begin());
luate.erase(luate.begin());
luate.insert({a[ri],ri});
sum_luate += a[ri];
}
else
neluate.insert({a[ri],ri});
while(!luate.empty() && 2*(ri-start) + (start-le) + (int)luate.size() > d)
{
sum_luate -= (*luate.begin()).first;
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()));
}
assert(le<=start);
assert(ri>=start);
}
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());
sum_luate=0;
int mnm=INF;
for(int i=0;i<v.size();i++)
{
mnm = min(mnm, v[i].second);
if(d - 2*(ri-start) - (start-mnm) < i+1)
{
for(int j=i;j<v.size();j++)
neluate.insert(v[j]);
break;
}
sum_luate += v[i].first;
luate.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();
}
}
/*int poz=1;
for(int ri=start;ri<=n;ri++)
{
while(poz+1<=start)
{
ll aux=0, unde=-1;
for(int pas=1;pas<=min(20,start-poz);pas++)
{
ll x = calc(poz+pas,ri);
if(x >= aux)
{
aux = x;
unde = pas;
}
}
if(aux < calc(poz,ri))
break;
poz+=unde;
}
mxm = max(mxm, calc(poz,ri));
}*/
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;
}
/*
intindem siru la dreapta lui start
dupa ce facem asta o sa avem: ramase = d - (ri-le)
lun + luate = d
ne fixam valoarea minima pe care o luam
0 - <lim
1 - >=lim
vrem sa luam un interval (le,ri) a.i. cnt[ri] - cnt[le-1] <= d - (ri-le)
*/
