#include"holiday.h"
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<ld,ll>
#define fi first
#define se second
ll const N=1e5+10;
vector<ll>a;
ll s;
ll n;
pii dp[N][2]={};
pii check(ld mid)
{
dp[s][0]={0,0};
dp[s][1]={a[s]-mid,1};
for (ll i=s-1;i>=0;i--)
{
dp[i][0]=max(make_pair(dp[i+1][0].first-mid,dp[i+1][0].se+1),make_pair(dp[i+1][1].first-mid,dp[i+1][1].se+1));
dp[i][1]=max(make_pair(dp[i+1][0].first-2*mid+a[i],dp[i+1][0].se+2),make_pair(dp[i+1][1].first-2*mid+a[i],dp[i+1][1].se+2));
}
if (s+1<n)
{
dp[s+1][0]={-1e9,0};
dp[s+1][1]={-1e9,0};
for (ll j=0;j<=s;j++)
{
dp[s+1][0]=max(dp[s+1][0],max(make_pair(dp[j][0].first-(s+1-j)*mid,dp[j][0].se+(s+1-j)),make_pair(dp[j][1].first-(s+1-j)*mid,dp[j][1].se+(s+1-j))));
dp[s+1][1]=max(dp[s+1][1],max(make_pair(dp[j][0].first-(s+1-j+1)*mid+a[s+1],dp[j][0].se+(s+1-j)+1),make_pair(dp[j][1].first-(s+1-j+1)*mid+a[s+1],dp[j][1].se+(s+1-j+1))));
}
}
for (ll i=s+2;i<n;i++)
{
dp[i][0]=max(make_pair(dp[i-1][0].first-mid,dp[i-1][0].se+1),make_pair(dp[i-1][1].first-mid,dp[i-1][1].se+1));
dp[i][1]=max(make_pair(dp[i-1][0].first-2*mid+a[i],dp[i-1][0].se+2),make_pair(dp[i-1][1].first-2*mid+a[i],dp[i-1][1].se+2));
}
pii ans={0,0};
for (ll i=0;i<n;i++)
{
ans=max(ans,{dp[i][0].fi+dp[i][0].se*mid,dp[i][0].se});
ans=max(ans,{dp[i][1].fi+dp[i][1].se*mid,dp[i][1].se});
}
return ans;
}
pii check2(ld mid)
{
dp[s][0]={0,0};
dp[s][1]={a[s]-mid,1};
for (ll i=s+1;i<n;i++)
{
dp[i][0]=max(make_pair(dp[i-1][0].first-mid,dp[i-1][0].se+1),make_pair(dp[i-1][1].first-mid,dp[i-1][1].se+1));
dp[i][1]=max(make_pair(dp[i-1][0].first-2*mid+a[i],dp[i-1][0].se+2),make_pair(dp[i-1][1].first-2*mid+a[i],dp[i-1][1].se+2));
}
if (s-1>=0)
{
dp[s-1][0]={-1e9,0};
dp[s-1][1]={-1e9,0};
for (ll j=s;j<n;j++)
{
dp[s-1][0]=max(dp[s-1][0],max(make_pair(dp[j][0].first-(j-s+1)*mid,dp[j][0].se+(j-s+1)),make_pair(dp[j][1].first-(j-s+1)*mid,dp[j][1].se+(j-s+1))));
dp[s-1][1]=max(dp[s-1][1],max(make_pair(dp[j][0].first-(j-s+2)*mid+a[s-1],dp[j][0].se+(j-s+1)+1),make_pair(dp[j][1].first-(j-s+2)*mid+a[s-1],dp[j][1].se+(j-s+2))));
}
}
for (ll i=s-2;i>=0;i--)
{
dp[i][0]=max(make_pair(dp[i+1][0].first-mid,dp[i+1][0].se+1),make_pair(dp[i+1][1].first-mid,dp[i+1][1].se+1));
dp[i][1]=max(make_pair(dp[i+1][0].first-2*mid+a[i],dp[i+1][0].se+2),make_pair(dp[i+1][1].first-2*mid+a[i],dp[i+1][1].se+2));
}
pii ans={0,0};
for (ll i=0;i<n;i++)
{
ans=max(ans,{dp[i][0].fi+dp[i][0].se*mid,dp[i][0].se});
ans=max(ans,{dp[i][1].fi+dp[i][1].se*mid,dp[i][1].se});
}
return ans;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[])
{
s=start;
n=N;
for (ll i=0;i<n;i++)
a.push_back(attraction[i]);
ld epi=1e-6;
ld st=-1e6,en=1e6+10;
while (st+epi<en)
{
ld mid=(st+en)/2.;
if (check(mid).se>d)
st=mid;
else
en=mid;
}
ld st1=-1e6,en1=1e6+10;
while (st1+epi<en1)
{
ld mid=(st1+en1)/2.;
if (check2(mid).se>d)
st1=mid;
else
en1=mid;
}
return max(check(en).fi,check2(en1).fi);
}
