#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;
}
ll solve()
{
ll mxm=0;
/*int le=1;
for(int ri=start;ri<=n;ri++)
{
while(le+1<=start && calc(le+1,ri) >= calc(le,ri))
le++;
mxm = max(mxm, calc(le,ri));
}*/
/*for(int le=start;le>0;le--)
for(int ri=start;ri<=n;ri++)
mxm = max(mxm, calc(le,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)
*/
