#include <bits/stdc++.h>
#include "holiday.h"
#define lp(i,a,b) for(int i=a;i<b;i ++)
#define MAXN 300005
#define pb push_back
#define pii pair<int,int>
#define ss second
#define ff first
#define lli long long int
using namespace std;
multiset<int> m ;
lli resp ;
int lastd[MAXN] , laste[MAXN];
void tira()
{
resp -= *m.begin() ;
m.erase(m.begin()) ;
}
lli calc (int n, int start, int d,int a[], int v)
{
resp = 0 ;
m.clear() ;
lli best = -1 ;
for(int i = start ; i < min(n,start+d) and i > max(start-d , -1 ) ; i += v)
{
m.insert(a[i]) ;
resp += a[i] ;
int k = m.size() ;
if( k - 1 > d - abs(i - start) )
tira() ;
if(k > d - abs(i - start) ) tira() ;
if( best < resp )
{
best = resp ;
if(v == 1) lastd[d] = i ;
else laste[d] = i ;
}
}
return best ;
}
long long int findMaxAttraction(int n, int start, int d,int a[])
{
if(start == 0) return calc(n,0,d,a,1) ;
lli best = -1;
lli vd[n+5] , ve[n+5];
lp(i,1,d+1){
vd[i] = calc(n , start, i , a, 1) ;
ve[i] = calc(n,start,i,a,-1) ;
}
lp(i,1,d+1)
{
//chuto se vai pra direita ou para esquerda
lli ans ;
//esquerda
ans = ve[i] ;
if( d - i - start + laste[i] - 1 > 0 ) ans += calc(n, start+1 , d - i - start+laste[i] - 1 , a, 1) ;
best = max(best, ans) ;
//direita
ans = vd[i] ;
if( d - i + lastd[i] - start -1 > 0 ) ans += calc(n, start-1 , d-i-lastd[i]+start - 1 , a , -1) ;
best = max(best, ans) ;
}
return best ;
}
