#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
{
int val = 0, active = 0;
Node() { val = 0, active = 0; }
Node(int _v, int _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;
pii b[MAXN];
Node ST[4*MAXN];
bool cmp(pii _a, pii _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];
}
int qry(int x, int node = 0, int l = 0, int r = N - 1)
{
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;
pii 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);
int maxim = 0, tmp = l;
for(int i = l; i <= r; i++)
{
upd(pos[i], 1);
int aux = qry(days-i+start);
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);
}
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;
solve(start, N - 1, 1, 2*N + min(start, N - start - 1));
return f[_d].second;
}
