#include"holiday.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 1e5 + 3;
long long d1[2][(int)3e5], d2[2][(int)3e5];
struct tree{
int cnt, l, r;
long long sum;
}
t[N * 19];
int n, a[N], sz, st, root[N], D;
vector <int> vec;
void update (int ov, int nv, int pos, int val, int tl = 0, int tr = n) {
if (tl == tr) {
t[nv].cnt = t[ov].cnt + 1;
t[nv].sum = t[ov].sum + val;
} else {
int tm = (tl + tr) >> 1;
if (pos <= tm) {
t[nv].r = t[ov].r;
t[nv].l = ++sz;
update( t[ov].l, t[nv].l, pos, val, tl, tm );
} else {
t[nv].l = t[ov].l;
t[nv].r = ++sz;
update( t[ov].r, t[nv].r, pos, val, tm + 1, tr );
}
t[nv].cnt = t[ t[nv].l ].cnt + t[ t[nv].r ].cnt;
t[nv].sum = t[ t[nv].l ].sum + t[ t[nv].r ].sum;
}
}
long long get (int ov, int nv, int k, int tl = 0, int tr = n) {
if (tl == tr) {
return min((t[nv].sum - t[ov].sum), k * 1ll * vec[tl]);
}
int tm = (tl + tr) >> 1;
if (t[t[nv].r].cnt - t[t[ov].r].cnt >= k) {
return get(t[ov].r, t[nv].r, k, tm + 1, tr);
}
return get(t[ov].l, t[nv].l, k - (t[t[nv].r].cnt - t[t[ov].r].cnt), tl, tm ) + t[t[nv].r].sum - t[t[ov].r].sum;
}
void solve1 (int opl, int opr, int dl, int dr) {
if (dl > dr) return;
int dm = (dl + dr) >> 1, opt;
long long res = 0, val;
for (int i = opl; i <= opr; i++) {
if ( dm - (i - st) <= 0 ) break;
val = get(root[st - 1], root[i], dm - (i - st));
if ( val > res ) {
res = val;
opt = i;
}
}
d1[0][dm] = res;
if (dm + (opt - st) <= D) d1[1][dm + (opt - st)] = res;
solve1(opl, opt, dl, dm - 1);
solve1(opt, opr, dm + 1, dr);
}
void solve2 (int opl, int opr, int dl, int dr) {
if (dl > dr || opl > opr) return;
int dm = (dl + dr) >> 1, opt;
long long res = 0, val;
for (int i = opr; i >= opl; i--) {
if ( dm - (st - i) <= 0 ) break;
val = get(root[i - 1], root[st - 1], dm - (st - i));
if ( val > res ) {
res = val;
opt = i;
}
}
d2[0][dm] = res;
if (dm + (st - opt) <= D) d2[1][dm + (st - opt)] = res;
solve2(opl, opt, dm + 1, dr);
solve2(opt, opr, dl, dm - 1);
}
long long findMaxAttraction(int A, int start, int ASD, int at[]) { start++; D = ASD;
n = A;
st = start;
for (int i = 0; i < n; i++) {
vec.pb(at[i]);
}
sort(all(vec));
vec.resize(unique(all(vec)) - vec.begin());
for (int i = 0; i < n; i++) {
a[i + 1] = lower_bound(all(vec), at[i]) - vec.begin();
root[i + 1] = ++sz;
update( root[i], root[i + 1], a[i + 1], vec[ a[i + 1] ] );
}
solve1(start, n, 1, min(D, 2 * (n - start) + 1) );
solve2(1, start - 1, 1, min(D, 2 * (start - 1) + 1) );
for (int i = 1; i <= D; i++) {
d1[0][i] = max(d1[0][i - 1], d1[0][i]);
d1[1][i] = max(d1[1][i - 1], d1[1][i]);
d2[0][i] = max(d2[0][i - 1], d2[0][i]);
d2[1][i] = max(d2[1][i - 1], d2[1][i]);
}
long long ans = 0;
for (int i = 0; i <= D; i++) {
ans = max(ans, d1[1][i] + d2[0][D - i]);
ans = max(ans, d1[0][i] + d2[1][D - i]);
}
return ans;
}
