#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;
struct node {
int val, size;
node *left, *right;
node() {
val = size = 0;
left = nullptr;
right = nullptr;
}
};
const int NN = 1e5, DD = 2 * NN + NN / 2;
map<int, int> m1, m2;
node* v[NN + 1];
int N, START, D, *ATTRACTION;
long long dp1[DD + 1], dp2[DD + 1], dp3[DD + 1], dp4[DD + 1];
int l1[DD + 1], l2[DD + 1], l3[DD + 1], l4[DD + 1];
void pre() {
int copy[N];
for (int i = 0; i < N; i++)
copy[i] = ATTRACTION[i];
sort(copy, copy + N);
set<int> s;
for (int i = 0, j = 0; i < N; i++) {
if (s.count(copy[i]))
continue;
m1[copy[i]] = j;
m2[j++] = copy[i];
}
}
void update(node *cur, node *prev, int tl, int tr, int l) {
if (l == tl && tl == tr) {
cur->val = prev->val + m2[l];
cur->size = prev->size + 1;
return;
}
int tm = (tl + tr) / 2;
if (l <= tm) {
cur->right = prev->right;
cur->left = new node();
update(cur->left, prev->left, tl, tm, l);
} else {
cur->left = prev->left;
cur->right = new node();
update(cur->right, prev->right, tm + 1, tr, l);
}
cur->val = cur->left->val + cur->right->val;
cur->size = cur->left->size + cur->right->size;
}
void build(node *n, int tl, int tr) {
if (tl == tr)
return;
n->left = new node();
n-> right = new node();
int tm = (tl + tr) / 2;
build(n->left, tl, tm);
build(n->right, tm + 1, tr);
}
void build() {
v[0] = new node();
build(v[0], 0, N - 1);
for (int i = 1; i <= N; i++) {
v[i] = new node();
update(v[i], v[i - 1], 0, N - 1, m1[ATTRACTION[i - 1]]);
}
}
long long query(node *n1, node *n2, int c) {
c = min(c, n2->size - n1->size);
if (c <= 0)
return 0;
if (n2->size - n1->size == c)
return n2->val - n1->val;
if (n2->right->size - n1->right->size >= c)
return query(n1->right, n2->right, c);
else
return query(n1->right, n2->right, n2->right->size - n1->right->size) + query(n1->left, n2->left, c - n2->right->size - n1->right->size);
}
/*void calc1() {
dp1[1] = dp1[2] = ATTRACTION[START];
l1[1] = l1[2] = START;
for (int i = 3; i <= D; i++) {
int t = query(v[l1[i - 1]], v[START + 1], i - 2 * (START - l1[i - 1])), j = l1[i - 1] - 1;
while (j >= 0) {
int temp = query(v[j], v[START + 1], i - 2 * (START - j));
if (temp < t)
break;
t = temp;
j--;
}
dp1[i] = t;
l1[i] = j == -1 ? 0 : j;
}
}*/
void calc1() {
pair<long long, int> best = {ATTRACTION[START], START};
for (int i = START - 1; i >= 0; i--)
best = max(best, {query(v[i], v[START + 1], D - 2 * (START - i)), i});
dp1[D] = best.first;
l1[D] = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[l1[i + 1]], v[START + 1], i - 2 * (START - l1[i + 1])), l1[i + 1]};
for (int j = l1[i + 1] + 1; j <= START; j++) {
pair<long long, int> temp = {query(v[j], v[START + 1], i - 2 * (START - j)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp1[i] = t.first;
l1[i] = t.second;
}
}
/*void calc2() {
dp2[1] = dp2[2] = ATTRACTION[START];
l2[1] = l2[2] = START;
for (int i = 3; i <= D; i++) {
int t = query(v[START], v[l2[i - 1] + 1], i - 2 * (l1[i - 1] - START)), j = l1[i - 1] + 1;
while (j < N) {
int temp = query(v[START], v[j + 1], i - 2 * (j - START));
if (temp < t)
break;
t = temp;
j++;
}
dp2[i] = t;
l2[i] = j == N ? N - 1 : j;
}
}*/
void calc2() {
pair<long long, int> best = {ATTRACTION[START], START};
for (int i = START + 1; i < N; i++)
best = max(best, {query(v[START], v[i + 1], D - 2 * (i - START)), i});
dp2[D] = best.first;
l2[D] = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[START], v[l2[i + 1] + 1], i - 2 * (l2[i + 1] - START)), l2[i + 1]};
for (int j = l2[i + 1] - 1; j >= START; j--) {
pair<long long, int> temp = {query(v[START], v[j + 1], i - 2 * (j - START)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp2[i] = t.first;
l2[i] = t.second;
}
}
/*void calc3() {
dp3[1] = ATTRACTION[START + 1];
l3[1] = START + 1;
for (int i = 2; i <= D; i++) {
int t = query(v[START + 1], v[l3[i - 1] + 1], i - (l3[i - 1] - START - 1)), j = l3[i - 1] + 1;
while (j < N) {
int temp = query(v[START + 1], v[j + 1], i - (j - START - 1));
if (temp < t)
break;
t = temp;
j++;
}
dp3[i] = t;
l3[i] = j == N ? N - 1 : j;
}
}*/
void calc3() {
pair<long long, int> best = {ATTRACTION[START + 1], START + 1};
for (int i = START + 2; i < N; i++)
best = max(best, {query(v[START + 1], v[i + 1], D - (i - START - 1)), i});
dp3[D] = best.first;
l3[D] = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[START + 1], v[l3[i + 1] + 1], i - (l3[i + 1] - START - 1)), l3[i + 1]};
for (int j = l3[i + 1] - 1; j >= START + 1; j--) {
pair<long long, int> temp = {query(v[START + 1], v[j + 1], i - (j - START - 1)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp3[i] = t.first;
l3[i] = t.second;
}
}
/*void calc4() {
dp4[1] = ATTRACTION[START - 1];
l4[1] = START - 1;
for (int i = 2; i <= D; i++) {
int t = query(v[l4[i - 1]], v[START], i - (START - 1 - l4[i - 1])), j = l4[i - 1] - 1;
while (j >= 0) {
int temp = query(v[j], v[START], i - (START - 1 - j));
if (temp < t)
break;
}
}
}*/
void calc4() {
pair<long long, int> best = {ATTRACTION[START - 1], START - 1};
for (int i = START - 2; i >= 0; i--)
best = max(best, {query(v[i], v[START], D - (START - 1 - i)), i});
dp4[D] = best.first;
l4[D] = best.second;
for (int i = D - 1; i >= 0; i--) {
pair<long long, int> t = {query(v[l4[i + 1]], v[START], i - (START - 1 - l4[i + 1])), l4[i + 1]};
for (int j = l4[i + 1] + 1; j <= START - 1; j++) {
pair<long long, int> temp = {query(v[j], v[START], i - (START - 1 - j)), j};
if (max(t, temp) == t)
break;
t = temp;
}
dp4[i] = t.first;
l4[i] = t.second;
}
}
long long answer() {
long long ans = max(dp1[D], dp2[D]);
for (int i = 0; i <= D - 1; i++) {
ans = max(ans, dp1[i] + dp3[D - i - 1]);
ans = max(ans, dp2[i] + dp4[D - i - 1]);
}
return ans;
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
START = start;
D = d;
ATTRACTION = attraction;
pre();
build();
calc1();
calc2();
if (START != N - 1)
calc3();
if (START)
calc4();
return answer();
}
/*int main() {
int n, start, d;
int attraction[100000];
int i, n_s;
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0 ; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
return 0;
}*/
