#include "holiday.h"
#include <bits/stdc++.h>
#define pb push_back
#define task "sequence"
#define pll pair<ll, ll>
#define pii pair<vector<ll>, ll>
#define fi first
#define se second
using ll = long long;
const long long mod = 1e15+7;
const ll mod1 = 1e9+1;
const ll N = 2e5+5;
const int base = 350;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, u, tong, v, a[N], ans, c[N], d[N], b[N], sum[N*4], cnt[N*4], s;
vector<ll> adj[N], kq;
vector<pll> l, r;
pll p[N];
void update(ll id, ll l, ll r, ll pos, ll u, ll v)
{
if(l == r)
{
cnt[id] = u;
sum[id] = v;
return;
}
ll mid = (l + r) / 2;
if(mid >= pos)update(id*2, l, mid, pos, u, v);
else update(id*2+1, mid+1, r, pos, u, v);
sum[id] = sum[id*2] + sum[id*2+1];
cnt[id] = cnt[id*2] + cnt[id*2+1];
}
ll get(ll id, ll l, ll r, ll k)
{
if(k < 0)return-mod;
if(k == 0)return 0;
if(cnt[id] <= k)return sum[id];
ll mid = (l + r) / 2;
if(cnt[id*2] < k)return get(id*2, l, mid, k);
else return sum[id*2] + get(id*2+1, mid+1, r, k-cnt[id*2]);
}
bool cmp(ll& x, ll& y)
{
return a[x] > a[y];
}
void add(ll cl, ll cr)
{
while(u < cl)
{
update(1, 1, n, b[u], 0, 0);
++u;
}
while(u > cl)
{
--u;
update(1, 1, n, b[u], 1, p[b[u]].fi);
}
while(v < cr)
{
++v;
update(1, 1, n, b[v], 1, p[b[v]].fi);
}
while(v > cr)
{
update(1, 1, n, b[v], 0, 0);
--v;
}
}
void call(ll l, ll r, ll opl, ll opr)
{
if(l > r)return;
ll mid = (l + r) / 2;
ll best = mid, val = -mod;
//cout << l <<" "<<r<<" "<<mid<<" "<<opl<< " "<<opr<<endl;
for(int i = opl; i <= min(min(mid, opr), s); i ++)
{
k = m - (mid-i+mid-s);
//cout << "ok"<<" ";
add(i, mid);
if(get(1, 1, n, k) > val)
{
val = get(1, 1, n, k);
best = i;
}
//cout << "ok" <<" ";
}
//cout << l <<" "<< r << " " << mid << endl;;
ans = max(ans, val);
call(l, mid-1, opl, best);
call(mid+1, r, best, opr);
}
void calr(ll l, ll r, ll opl, ll opr)
{
if(l > r)return;
ll mid = (l + r) / 2;
ll best = mid, val = -mod;
for(int i = opl; i <= min(min(mid, opr), s); i ++)
{
k = m - (mid-i+s-i);
if(k <= 0)continue;
add(i, mid);
if(get(1, 1, n, k) > val)
{
val = get(1, 1, n, k);
best = i;
}
}
ans = max(ans, val);
calr(l, mid-1, opl, best);
calr(mid+1, r, best, opr);
}
ll findMaxAttraction(int _n, int start, int _d, int attraction[])
{
n = _n;
s = start+1;
m = _d;
for(int i = 1; i <= n; i ++)
{
p[i].fi = -attraction[i-1];
p[i].se = i;
}
sort(p+1, p+1+n);
for(int i = 1; i <= n; i ++)
{
p[i].fi *= -1;
b[p[i].se] = i;
}
u = 2, v = 1;
ans = -mod;
call(s, n, 1, n);
fill_n(sum, n*4+2, 0);
fill_n(cnt, n*4+2, 0);
u = 2, v = 1;
calr(s, n, 1, n);
return ans;
}
