//#include"holiday.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
ll n, x, z, cl, cr, f, G[100000];
queue <array<ll, 4>> Q[2];
array <ll, 2> A[100000];
struct SegTree{
vector <ll> st{vector <ll> (400000, 0)};
vector <ll> cnt{vector <ll> (400000, 0)};
void update(ll id, ll l, ll r, ll q, bool b) {
if (l == r) {
if (b) st[id] = A[l][0], cnt[id] = 1;
else st[id] = cnt[id] = 0;
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, b);
else update(id*2+1, mid+1, r, q, b);
st[id] = st[id*2] + st[id*2+1];
cnt[id] = cnt[id*2] + cnt[id*2+1];
}
ll k;
ll init_query(ll K) {
k = K;
return kth_query(1, 0, n-1);
}
ll kth_query(ll id, ll l, ll r) {
if (k >= cnt[id]) {
k -= cnt[id];
return st[id];
}
if (l == r) return 0;
ll mid = (l+r)/2;
if (cnt[id*2] >= k) return kth_query(id*2, l, mid);
else {
k -= cnt[id*2];
return st[id*2] + kth_query(id*2+1, mid+1, r);
}
}
}ST;
ll solve(ll l, ll r, ll optL, ll optR) {
ll mid = (l+r)/2;
while (cl < mid) {
ST.update(1, 0, n-1, G[cl], 0);
++cl;
}
cr = max(cr, mid);
while (cr < optL) {
ST.update(1, 0, n-1, G[cr], 1);
++cr;
}
ll opt = -1, optVal = -1, cur, m = z-(x-mid)-max(0LL, optL-mid);
for (int i=max(mid, optL); i<=optR; ++i) {
if (m <= 0) break;
ST.update(1, 0, n-1, G[i], 1);
cur = ST.init_query(m);
if (cur >= optVal) {
opt = i;
optVal = cur;
}
--m;
}
for (int i=max(mid, optL); i<=optR; ++i) {
ST.update(1, 0, n-1, G[i], 0);
}
//cout << mid << " " << optVal << " " << opt << endl;
if (l != mid) Q[1].push({l, mid-1, optL, opt});
if (mid != r) Q[1].push({mid+1, r, opt, optR});
return optVal;
}
void sharky() {
Q[0].push({0, x, 0, n-1});
while (!Q[0].empty()) {
cl = cr = 0;
while (!Q[0].empty()) {
auto [l, r, ql, qr] = Q[0].front();
Q[0].pop();
f = max(f, solve(l, r, ql, qr));
}
swap(Q[0], Q[1]);
while (cl < cr) {
ST.update(1, 0, n-1, G[cl], 0);
++cl;
}
}
}
long long int findMaxAttraction(int _n, int start, int d, int attraction[]) {
n = _n, x = start, z = d;
for (int i=0; i<n; ++i) A[i] = {attraction[i], i};
sort(A, A+n, [](auto a, auto b) {
return a[0] > b[0];
});
for (int i=0; i<n; ++i) {
G[A[i][1]] = i;
}
sharky();
for (int i=0; i<n/2; ++i) {
swap(G[i], G[n-1-i]);
}
x = n-1-x;
sharky();
return f;
}
