//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;
struct Segment_Tree {
int m;
pair<int, ll> st[N << 2];
void init (int n) {
m = n;
rep (i, 1, n << 2) st[i].fs = st[i].se = 0;
}
pair<int, ll> mer (pair<int, ll> lc, pair<int, ll> rc) {
pair<int, ll> cur;
cur.fs = lc.fs + rc.fs;
cur.se = lc.se + rc.se;
return cur;
}
void update (int id, int l, int r, int pos, ll val) {
if (l > pos || r < pos) return;
if (l == r) {
st[id].se += val;
if (val < 0) --st[id].fs;
else ++st[id].fs;
return;
}
int mid = l + r >> 1;
update (id << 1, l, mid, pos, val);
update (id << 1 | 1, mid + 1, r, pos, val);
st[id] = mer(st[id << 1], st[id << 1 | 1]);
}
ll walk (int id, int l, int r, int delta) {
if (st[id].fs <= delta) return st[id].se;
if (l == r) return 0;
int mid = l + r >> 1;
ll res = walk (id << 1 | 1, mid + 1, r, delta);
if (st[id << 1 | 1].fs <= delta) {
res += walk (id << 1, l, mid, delta - st[id << 1 | 1].fs);
}
return res;
}
void update (int pos, ll val) {
if (val == 0) return;
update (1, 1, m, pos, val);
}
ll walk (int delta) {
return walk(1, 1, m, delta);
}
}ST;
int cL = 1, cR = 0;
int n, St, D;
pii a[N];
ll dp[N];
int opt[N];
vector<pii> vec;
void go (int L, int R) {
assert(L <= R);
while (cL < L) {
ST.update (a[cL].se, -a[cL].fs);
++cL;
}
while (cL > L) {
--cL;
ST.update (a[cL].se, a[cL].fs);
}
while (cR < R) {
++cR;
ST.update (a[cR].se, a[cR].fs);
}
while (cR > R) {
ST.update (a[cR].se, -a[cR].fs);
--cR;
}
}
void dnc (int L, int R, int optL, int optR) {
if (L > R) return;
int mid = L + R >> 1;
ll best = -1;
rep (i, optL, optR) {
if(mid < i) go (mid, i);
else go (i, mid);
int delta = abs((mid - St) * 2 + St - i);
ll curcost = ST.walk(D - delta);
if (curcost > best) {
best = curcost;
opt[mid] = i;
}
}
dp[mid] = best;
dnc(L, mid - 1, optL, opt[mid]);
dnc(mid + 1, R, opt[mid], optR);
}
ll process () {
rep (i, 1, n) dp[i] = 0;
ST.init(n), cL = 1, cR = 0;
dnc (St + 1, n, 1, St);
ST.init(n), cL = 1, cR = 0;
dnc (1, St - 1, St, n);
//
ST.init(n), cL = 1, cR = 0;
rep (i, St, n) {
go (St, i);
int delta = i - St;
ll curcost = ST.walk(D - delta);
dp[St] = max(dp[St], curcost);
}
ST.init(n), cL = 1, cR = 0;
rep (i, 1, St) {
go (i, St);
int delta = St - i;
ll curcost = ST.walk(D - delta);
dp[St] = max(dp[St], curcost);
}
return *max_element(dp + 1, dp + 1 + n);
}
ll findMaxAttraction (int _n, int _St, int _D, int _a[]) {
//void solution () {
// cin >> n >> St >> D;
n = _n;
St = _St;
D = _D;
++St;
rep (i, 1, n) {
// cin >> a[i].fs;
a[i].fs = _a[i - 1];
vec.pb(MP(a[i].fs, i));
}
sort (ALL(vec));
rep (i, 1, n) {
a[i].se = lower_bound(ALL(vec), MP(a[i].fs, i)) - vec.begin() + 1;
}
ll Ans = process();
reverse(a + 1, a + 1 + n);
St = n - St + 1;
Ans = max(Ans, process());
return Ans;
// cout << Ans<<"\n";
}
//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
//// file("c");
// ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
100 0 150
4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13
*/
