#include "holiday.h"
/*
* Author: Nonoze
* Created: Tuesday 28/04/2026
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef DEBUG
#define dbg(...)
#else
#include "grader.cpp"
#endif
#define cout cerr
#define quit(x) return (void)(cout << x << endl)
template<typename T> void read(T& x) { cin >> x; }
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second); }
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(v) sort(all(v)), v.erase(unique(all(v)), (v).end())
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define QYES quit("YES")
#define QNO quit("NO")
#define int long long
#define double long double
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=20;
struct SegTree {
int n;
vector<int> t, val, on;
SegTree(int _n) {
n=_n, t.resize(4*n, 0), on.resize(4*n, 0), val.resize(n);
}
void build(int v, int l, int r, vector<pair<int, int>>& a) {
if (l==r) {
val[l]=a[l].fi;
return;
}
int mid=(l+r)/2;
build(2*v, l, mid, a);
build(2*v+1, mid+1, r, a);
on[v]=on[2*v]+on[2*v+1];
}
void update(int pos) { update(1, 0, n-1, pos); }
void update(int v, int l, int r, int pos) {
if (l==r) {
on[v]^=1;
t[v]=on[v]*val[l];
return;
}
int mid=(l+r)/2;
if (pos<=mid) update(2*v, l, mid, pos);
else update(2*v+1, mid+1, r, pos);
t[v]=t[2*v]+t[2*v+1];
on[v]=on[2*v]+on[2*v+1];
}
int query(int nb) { return query(1, 0, n-1, nb); }
int query(int v, int l, int r, int nb) {
if (on[v]<=nb) return t[v];
if (l==r) return 0;
int mid=(l+r)/2;
int ans=query(2*v, l, mid, nb);
if (nb>on[2*v]) ans+=query(2*v+1, mid+1, r, nb-on[2*v]);
return ans;
}
} st(0);
int bl=0, br=-1;
vector<int> empl;
void toggle(int x) { st.update(empl[x]); }
void modify(int l, int r) {
while (br<r) toggle(++br);
while (bl>l) toggle(--bl);
while (br>r) toggle(br--);
while (bl<l) toggle(bl++);
}
int n, start;
vector<int> a;
vector<int> dpl, dpr; // dp[i][j] = max attraction if we go from start to i and we use j attractions
void DC(int l, int r, int optl, int optr) {
if (l>r || optr<optl) return;
int mid=(l+r)/2;
pair<int, int> best={0, optl};
for (int k=optl; k<=optr&&mid>=2*(k-start); k++) {
modify(start, k);
int sm=st.query(mid-2*(k-start));
if (sm>best.fi) best={sm, k};
}
dpr[mid]=best.fi;
DC(l, mid-1, optl, best.se);
DC(mid+1, r, best.se, optr);
}
void DC2(int l, int r, int optl, int optr) {
if (l>r || optr<optl) return;
int mid=(l+r)/2;
pair<int, int> best={0, optr};
for (int k=optr; k>=optl&&mid>=(start-k); k--) {
modify(k, start-1);
int sm=st.query(mid-(start-k));
if (sm>=best.fi) best={sm, k};
}
dpl[mid]=best.fi;
DC2(mid+1, r, optl, best.se);
DC2(l, mid-1, best.se, optr);
}
int calc(int k) {
vector<pair<int, int>> temp;
for (int i=0; i<n; i++) temp.pb({a[i], i});
sort(rall(temp));
empl.resize(n);
for (int i=0; i<n; i++) empl[temp[i].se]=i;
st=SegTree(n); st.build(1, 0, n-1, temp);
dpl.clear(), dpr.clear();
dpl.resize(k+1, 0), dpr.resize(k+1, 0);
bl=0, br=-1;
DC(0, k, start, n-1);
DC2(0, k, 0, start-1);
int ans=0;
for (int i=0; i<=k; i++) cmax(ans, dpl[i]+dpr[k-i]);
return ans;
}
int findMaxAttraction(signed _n, signed _start, signed k, signed attraction[]) { n=_n; start=_start;
for (int i=0; i<n; i++) a.pb(attraction[i]);
int ans=calc(k); reverse(all(a)); start=n-1-start;
return max(ans, calc(k));
}
