#include"holiday.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=99824LL;
ll findMaxAttraction(int n, int start_pos, int days, int attraction[])
{
ll N = (ll) n; ll start = (ll) start_pos; ll d = (ll) days; vector<ll> a; REP(i,0,N) {a.pb((ll) attraction[i]);}
multiset<pl> s; ll ans=0LL;
for(ll l=start;l>=0;l--)
{
ll val=0LL;
s.clear();
ll r=2*start-l;
if(r>=N) {break;}
ll dl = d - 3*(start-l);
while(dl>r-l+1) {r++; if(r==N) {r--; break;} dl--;}
REP(i,l,r+1) {s.insert(mp(a[i],0));}
ll sum=0LL; multiset<pl>::iterator it=s.end();
REP(i,0,dl) {it--; sum+=(it->ff); if(it==s.begin()) {break;}} val=sum;
while(r<N-1)
{
r++; dl--; if(dl==0) {break;} s.insert(mp(a[r],it->ss-1));
if(a[r]>it->ff)
{
sum+=a[r]; sum-=(it->ff); it++; sum-=(it->ff); it++;
}
else if(a[r]<=it->ff)
{
sum-=(it->ff); it++;
}
val=max(val,sum);
}
ans=max(ans,val);
}
s.clear();
for(ll r=start;r<N;r++)
{
ll val=0LL;
s.clear();
ll l=2*start-r;
if(l<0) {break;}
ll dl = d - 3*(r-start);
while(dl>r-l+1) {l--; if(l<0) {l++; break;} dl--;}
REP(i,l,r+1) {s.insert(mp(a[i],0));}
ll sum=0LL; multiset<pl>::iterator it=s.end();
REP(i,0,dl) {it--; sum+=(it->ff); if(it==s.begin()) {break;}} val=sum;
while(l>0)
{
l--; dl--; if(dl==0) {break;} s.insert(mp(a[r],it->ss-1));
if(a[l]>it->ff)
{
sum+=a[l]; sum-=(it->ff); it++; sum-=(it->ff); it++;
}
else
{
sum-=(it->ff); it++;
}
val=max(val,sum);
}
ans=max(ans,val);
}
return ans;
}
