#include"holiday.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
struct Node
{
ll val = 0, active = 0;
Node() { val = 0, active = 0; }
Node(ll _v, ll _a) { val = _v; active = _a; }
Node operator+ (const Node& _x) const
{
return {val + _x.val, active + _x.active};
}
};
const int MAXN = 1e5 + 5;
int N, a[MAXN], pos[MAXN], D;
pll b[MAXN];
Node ST[4*MAXN];
bool cmp(pll _a, pll _b)
{
if(_a.first == _b.first)
return _a.second < _b.second;
return _a.first > _b.first;
}
void upd(int pos, int x, int node = 0, int l = 0, int r = N - 1)
{
if(r < pos || pos < l)
return;
if(l == r)
{
if(x)
ST[node].val = b[l].first;
else
ST[node].val = 0;
ST[node].active = x;
return;
}
int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2;
upd(pos, x, lchild, l, mid);
upd(pos, x, rchild, mid + 1, r);
ST[node] = ST[lchild] + ST[rchild];
}
ll qry(int x, int node = 0, int l = 0, int r = N - 1)
{
if(x < 0)
return -(1LL << 60LL);
if(x == 0)
return 0;
if(l == r)
return ST[node].val;
int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2;
if(ST[lchild].active <= x)
return ST[lchild].val + qry(x - ST[lchild].active, rchild, mid + 1, r);
else
return qry(x, lchild, l, mid);
}
int start;
pll f[3*MAXN], g[3*MAXN];
void solve(int l, int r, int l1, int r1)
{
if(l1 > r1)
return;
int days = (l1 + r1)/2;
for(int i = l; i <= r; i++)
upd(pos[i], 0);
ll maxim = 0, tmp = l;
for(int i = l; i <= r; i++)
{
if(days-i+start+1 < 0)
break;
upd(pos[i], 1);
ll aux = qry(days-i+start+1);
if(aux > maxim)
{
maxim = aux;
tmp = i;
}
}
f[days] = {tmp, maxim};
for(int i = l; i <= r; i++)
upd(pos[i], 0);
solve(l, f[days].first, l1, days - 1);
for(int i = l; i < f[days].first; i++)
upd(pos[i], 1);
solve(f[days].first, r, days + 1, r1);
}
void solve2(int l, int r, int l1, int r1)
{
if(l1 > r1)
return;
int days = (l1 + r1)/2;
for(int i = r; i >= l; i--)
upd(pos[i], 0);
ll maxim = 0, tmp = r;
for(int i = r; i >= l; i--)
{
if(days-start+1+i < 0)
break;
upd(pos[i], 1);
ll aux = qry(days-start+1+i);
if(aux > maxim)
{
maxim = aux;
tmp = i;
}
}
g[days] = {tmp, maxim};
for(int i = r; i >= l; i--)
upd(pos[i], 0);
solve2(g[days].first, r, l1, days - 1);
for(int i = g[days].first + 1; i <= r; i++)
upd(pos[i], 1);
solve2(l, g[days].first, days + 1, r1);
}
ll findMaxAttraction(int _n, int _start, int _d, int att[])
{
N = _n;
D = _d;
start = _start;
for(int i = 0; i < N; i++)
{
a[i] = att[i];
b[i] = {att[i], i};
}
sort(b, b + N, cmp);
for(int i = 0; i < N; i++)
pos[b[i].second] = i;
for(int i = 0; i < N; i++)
upd(i, 0);
solve(start + 1, N - 1, 0, D);
for(int i = 0; i < N; i++)
upd(i, 0);
solve2(0, start - 1, 0, D);
if(!D)
return 0;
ll ans = a[start];
for(int i = 0; i <= D; i++)
{
if(D - i - 2 - f[i].first - start >= 0)
ans = max(ans, g[D - i - 2 - f[i].first - start].second + f[i].second);
if(D - i - 2 - start + g[i].first >= 0)
ans = max(ans, f[D - i - 2 - start + g[i].first].second + g[i].second);
if(i > 0)
{
--i;
if(D - i - 2 - f[i].first - start >= 0)
ans = max(ans, g[D - i - 2 - f[i].first - start].second + f[i].second + a[start]);
if(D - i - 2 - start + g[i].first >= 0)
ans = max(ans, f[D - i - 2 - start + g[i].first].second + g[i].second + a[start]);
++i;
}
}
return ans;
}
