#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline T range(T l, T r) {
return uniform_int_distribution<T>(l, r)(rng);
}
inline void setin(string s) {
freopen(s.c_str(), "r", stdin);
}
inline void setout(string s) {
freopen(s.c_str(), "w", stdout);
}
template <typename T> void Min(T &a, T b) {
a = min(a, b);
}
template <typename T> void Max(T &a, T b) {
a = max(a, b);
}
const int inf = 1e9;
const int mod = 998244353;
const int N = 1e5 + 15;
int a[N];
multiset <int> now1, now2;
ll sum1, sum2;
struct node {
node *l, *r;
ll sum;
int cnt;
inline void copy(node *t) {
if(t)
l = t->l, r = t->r, sum = t->sum, cnt = t->cnt;
else
l = r = NULL, sum = 0, cnt = 0;
}
node(node *_l = NULL, node *_r = NULL) {
l = _l, r = _r;
sum = cnt = 0;
if(l)
sum += l->sum, cnt += l->cnt;
if(r)
sum += r->sum, cnt += r->cnt;
}
};
typedef node* pnode;
vector <pnode> root = {NULL};
inline int get_cnt(pnode t) {
return t ? t->cnt : 0;
}
inline ll get_sum(pnode t) {
return t ? t->sum : 0LL;
}
inline pnode get_r(pnode t) {
return t ? t->r : t;
}
inline pnode get_l(pnode t) {
return t ? t->l : t;
}
pnode update(pnode t, int tl, int tr, int pos) {
if(tl == tr) {
pnode nw = new node(t);
++nw->cnt, nw->sum += tl;
return nw;
}
int mid = tl + tr >> 1;
if(pos <= mid)
return new node(update(get_l(t), tl, mid, pos), get_r(t));
return new node(get_l(t), update(get_r(t), mid + 1, tr, pos));
}
ll get_sum_of_k(pnode t1, pnode t2, int tl, int tr, int k) {
if(k <= 0)
return 0;
int cnt = get_cnt(t2) - get_cnt(t1);
if(cnt <= k)
return get_sum(t2) - get_sum(t1);
if(tl == tr)
return 1LL * k * tl;
int mid = tl + tr >> 1;
int cntr = get_cnt(get_r(t2)) - get_cnt(get_r(t1));
return get_sum_of_k(get_l(t1), get_l(t2), tl, mid, k - cntr) + get_sum_of_k(get_r(t1), get_r(t2), mid + 1, tr, k);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
for(int i = 0; i < n; ++i)
a[i+1] = attraction[i];
for(int i = 1; i <= n; ++i) {
pnode t = root.back();
root.pb(update(t, 1, inf, a[i]));
}
++start;
ll ans = 0;
for(int i = start; i <= n; ++i) {
Max(ans, get_sum_of_k(root[start - 1], root[i], 1, inf, d - (i - start)));
for(int j = start - 1; j >= 1; --j)
Max(ans, get_sum_of_k(root[j - 1], root[i], 1, inf, d - (i - j) - (i - start)));
}
for(int i = start; i >= 1; --i) {
Max(ans, get_sum_of_k(root[i - 1], root[start], 1, inf, d - (start - i)));
for(int j = start + 1; j <= n; ++j)
Max(ans, get_sum_of_k(root[i - 1], root[j], 1, inf, d - (j - i) - (start - i)));
}
return ans;
}
