#include"holiday.h"
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
#define ll long long
ll const N=1e5+10;
vector<ll>a;
ll st;
ll n;
long long int findMaxAttraction(int N, int start, int d, int attraction[])
{
st=start;
n=N;
for (ll i=0;i<n;i++)
a.push_back(attraction[i]);
multiset<int>s;
ll ans=0;
ll cur=0;
for (int i=st;i<n;i++)
{
s.insert(a[i]);
cur+=a[i];
while (s.size()&&s.size()+i-st>d)
{
cur-=*begin(s);
s.erase(begin(s));
}
ans=max(ans,cur);
}
cur=0;
s={};
for (int i=st;i>=0;i--)
{
s.insert(a[i]);
cur+=a[i];
while (s.size()&&s.size()+st-i>d)
{
cur-=*begin(s);
s.erase(begin(s));
}
ans=max(ans,cur);
}
if (st!=0&&st!=n-1)
{
for (int l=0;l<st;l++)
{
s={};
cur=0;
for(int j=l;j<=st;j++)
{
cur+=a[j];
s.insert(a[j]);
}
for (int r=st+1;r<n;r++)
{
s.insert(a[r]);
cur+=a[r];
while (s.size()&&s.size()+(r-st)+(st-l)+min(r-st,st-l)>d)
{
cur-=*begin(s);
s.erase(begin(s));
}
ans=max(ans,cur);
}
}
}
return ans;
}
