#include "holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int segl[4*100005], seglco[4*100005], segr[4*100005], segrco[4*100005];
void updatel(int n, int l, int r, int i, int v, int c) {
if (l == r) {
if (c == 0) {
segl[n] = 0;
seglco[n] = 0;
} else {
segl[n] = v;
seglco[n] = 1;
}
} else {
int m = (l+r)/2;
if (l <= i && i <= m) {
updatel(2*n, l, m, i, v, c);
} else {
updatel(2*n+1, m+1, r, i, v, c);
}
segl[n] = segl[2*n] + segl[2*n+1];
seglco[n] = seglco[2*n] + seglco[2*n+1];
}
}
void updater(int n, int l, int r, int i, int v, int c) {
if (l == r) {
if (c == 0) {
segr[n] = 0;
segrco[n] = 0;
} else {
segr[n] = v;
segrco[n] = 1;
}
} else {
int m = (l+r)/2;
if (l <= i && i <= m) {
updater(2*n, l, m, i, v, c);
} else {
updater(2*n+1, m+1, r, i, v, c);
}
segr[n] = segr[2*n] + segr[2*n+1];
segrco[n] = segrco[2*n] + segrco[2*n+1];
}
}
int queryl(int n, int l, int r, int k) {
if (seglco[n] <= k) {
return segl[n];
} else {
int m = (l+r)/2, v = 0;
if (seglco[2*n+1] >= k) {
return queryl(2*n+1, m+1, r, k);
} else {
v += queryl(2*n+1, m+1, r, seglco[2*n+1]);
k -= seglco[2*n+1];
v += queryl(2*n, l, m, k);
return v;
}
}
}
int queryr(int n, int l, int r, int k) {
if (segrco[n] <= k) {
return segr[n];
} else {
int m = (l+r)/2, v = 0;
if (segrco[2*n+1] >= k) {
return queryr(2*n+1, m+1, r, k);
} else {
v += queryr(2*n+1, m+1, r, segrco[2*n+1]);
k -= segrco[2*n+1];
v += queryr(2*n, l, m, k);
return v;
}
}
}
int n, d, st, l[200005], r[200005], at[200005];
pair<int, int> dpl[200005], dpr[200005];
void calcl(int ld, int rd, int li, int ri) {
int m = (ld+rd)/2;
for (int i = li; i <= ri; i++) {
updatel(1, 0, n-1, l[i], at[i], 0);
}
for (int i = ri; i >= li; i--) {
if (m-(st-i) <= 0) {
break;
}
updatel(1, 0, n-1, l[i], at[i], 1);
int v = queryl(1, 0, n-1, m-(st-i));
if (v == dpl[m].first && dpl[m].second < i) {
dpl[m].second = i;
} else if (v > dpl[m].first) {
dpl[m].first = v;
dpl[m].second = i;
}
}
for (int i = li; i <= ri; i++) {
updatel(1, 0, n-1, l[i], at[i], 0);
}
if (ld != rd) {
calcl(ld, m, dpl[m].second, ri);
for (int i = dpl[m].second; i <= ri; i++) {
updatel(1, 0, n-1, l[i], at[i], 1);
}
calcl(m+1, rd, li, dpl[m].second);
}
}
void calcr(int ld, int rd, int li, int ri) {
int m = (ld+rd)/2;
for (int i = li; i <= ri; i++) {
updater(1, 0, n-1, r[i], at[i], 0);
}
for (int i = li; i <= ri; i++) {
if (m-(i-st) <= 0) {
break;
}
updater(1, 0, n-1, r[i], at[i], 1);
int v = queryr(1, 0, n-1, m-(i-st));
if (v == dpr[m].first && dpr[m].second > i) {
dpr[m].second = i;
} else if (v > dpr[m].first) {
dpr[m].first = v;
dpr[m].second = i;
}
}
for (int i = li; i <= ri; i++) {
updater(1, 0, n-1, r[i], at[i], 0);
}
if (ld != rd) {
calcr(ld, m, li, dpr[m].second);
for (int i = li; i <= dpr[m].second; i++) {
updater(1, 0, n-1, r[i], at[i], 1);
}
calcr(m+1, rd, dpr[m].second, ri);
}
}
int findMaxAttraction(int32_t N, int32_t ST, int32_t D, int32_t attraction[]) {
int ans = 0;
n = N;
d = D;
st = ST;
if (D == 0) {
return 0;
}
vector<pair<int, int>> lat, rat;
for (int i = 0; i < n; i++) {
at[i] = attraction[i];
}
for (int i = 0; i < st; i++) {
lat.push_back({at[i], i});
}
for (int i = st; i < n; i++) {
rat.push_back({at[i], i});
}
sort(lat.begin(), lat.end());
sort(rat.begin(), rat.end());
for (int i = 0; i < lat.size(); i++) {
l[lat[i].second] = i;
}
for (int i = 0; i < rat.size(); i++) {
r[rat[i].second] = i;
}
//for (int i = 0; i <= d; i++) {
// dpl[i] = {0, st-1};
// dpr[i] = {0, st};
//}
calcr(1, d, st, n-1);
if (st == 0) {
return dpr[d].first;
}
calcl(1, d, 0, st-1);
for (int i = 1; i <= d; i++) {
int l = dpl[i].second, r = dpr[i].second, dl, dr;
dl = max(d-(i+(st-l)), 0LL);
dr = max(d-(i+(r-st)), 0LL);
ans = max(ans, max(dpl[i].first+dpr[dl].first, dpr[i].first+dpl[dr].first));
}
return ans;
}
