#include <bits/stdc++.h>
#ifndef LOCAL
#include <holiday.h>
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
const ll inf = 1e18;
struct node{
node* left, *right;
int cnt;
ll sum;
node(int cnt = 0, ll sum = 0) : cnt(cnt), sum(sum), left(nullptr), right(nullptr) {}
node(node *left, node *right) : left(left), right(right), cnt((left -> cnt) + (right -> cnt)), sum((left -> sum) + (right -> sum)) {}
};
node *build(int l, int r){
if(l == r) return new node();
int mid = l + r >> 1;
return new node(build(l, mid), build(mid + 1, r));
}
vector<int> values;
node* update(node* p, int l, int r, int pos){
if(l == r){
return new node(p -> cnt + 1, p -> sum + values[l]);
}
int mid = l + r >> 1;
if(pos <= mid) return new node(update(p -> left, l, mid, pos), p -> right);
else return new node(p -> left, update(p -> right, mid + 1, r, pos));
}
ll query(node* pL, node* pR, int l, int r, int k){
if(l == r) return (pR -> sum - pL -> sum);
int mid = l + r >> 1;
int rightHave = (pR -> right -> cnt) - (pL -> right -> cnt); //prioritize right first
ll rightSum = (pR -> right -> sum) - (pL -> right -> sum);
if(k > rightHave) return rightSum + query(pL -> left, pR -> left, l, mid, k - rightHave);
else return query(pL -> right, pR -> right, mid + 1, r, k);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]){
++start;
vector<int> a(n + 1);
for(int i = 1; i <= n; ++i){
a[i] = attraction[i - 1];
values.push_back(a[i]);
}
sort(all(values));
compact(values);
for(int i = 1; i <= n; ++i){
a[i] = lower_bound(all(values), a[i]) - values.begin();
}
int m = sz(values) - 1;
vector<node*> roots;
roots.push_back(build(0, m));
for(int i = 1; i <= n; ++i){
roots.push_back(update(roots.back(), 0, m, a[i]));
}
ll ans = -inf;
auto solve = [&](){
auto query_cost = [&](int l, int r){
int moves = (r - l + min(r - start, start - l)); //choosing first direction
if(moves > d) return -inf;
int can_take = min(r - l + 1, d - moves);
ll ret = query(roots[l - 1], roots[r], 0, m, can_take);
return ret;
};
function<void(int, int, int, int)> dnc = [&](int l, int r, int optL, int optR){
int mid = l + r >> 1;
pair<ll, int> opt = {-inf, optL};
for(int i = optL; i <= optR; ++i){
opt = max(opt, {query_cost(mid, i), -i});
}
ans = max(ans, opt.first);
if(l < mid) dnc(l, mid - 1, -opt.second, optR);
if(mid < r) dnc(mid + 1, r, optL, -opt.second);
};
dnc(1, start, start, n);
};
solve();
// reverse(a + 1, a + 1 + n);
// start = n - start + 1;
// solve();
return ans;
}
#ifdef LOCAL
int main(){
int n = 5, start = 2, d = 7;
int attraction[] = {10, 2, 20, 30, 1};
cout << findMaxAttraction(n, start, d, attraction);
return 0;
}
#endif
