#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
typedef long long ll;
bool smax(ll &a, ll b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int N = 1e5 + 10;
int S[N], m;
ll seg[N << 2], sum[N << 2];
void build(int l = 0, int r = m, int id = 1) {
seg[id] = sum[id] = 0;
if (l == r - 1) return;
int mid = l + r >> 1;
build(l , mid , id << 1);
build(mid , r, id << 1 | 1);
}
void segAdd(int pos , int l = 0 , int r = m , int id = 1) {
if (l == r - 1) {
seg[id]++;
sum[id] += S[l];
return;
}
int mid = l + r >> 1;
if (pos < mid) segAdd(pos , l, mid , id << 1);
else segAdd(pos , mid , r, id <<1 | 1);
seg[id] = seg[id <<1] + seg[id <<1 | 1];
sum[id] = sum[id << 1] + sum[id <<1 | 1];
}
ll segGet(int &rem , int l = 0, int r = m, int id = 1) {
if (rem <= 0) return 0;
if (rem >= seg[id]) {
rem -= seg[id];
return sum[id];
}
if (l == r - 1) {
ll rem2 = rem;
rem = 0;
return rem2 * S[l];
}
int mid = l +r >> 1;
ll res = segGet(rem , mid , r ,id << 1 | 1);
res += segGet(rem , l , mid , id <<1 ) ;
return res;
}
ll ans[4][N << 2];
struct dat {
int l , r , s , t;
dat (int s_ , int t_, int l_, int r_) {
s = s_;
t = t_;
l = l_;
r = r_;
}
};
ll A[N], n, d;
void bfs(int beg, ll res[], int cost) {
build();
queue<dat> q;
fill(res , res + d + 1 , -1e18);
q.push(dat(0 , d + 1 , beg , n));
int last = beg;
while (!q.empty()) {
auto me = q.front();
q.pop();
int mid = me.s + me.t >> 1;
if (last > me.l + 1) {
build();
last = beg;
}
int best = me.l;
rep(i , me.l , me.r) {
while (last <= i) {
int id = lower_bound(S , S + m, A[last]) - S;
segAdd(id);
last++;
}
int rem = mid - (i - beg + 1) * cost;
if (smax(res[mid] , segGet(rem)))
best = i;
}
if (mid != me.s) q.push(dat(me.s , mid , me.l , best + 1));
if (mid != me.t - 1) q.push(dat(mid + 1 , me.t , best , me.r));
}
}
ll findMaxAttraction(int n2, int St, int d2, int A2[]) {
n = n2;
d = d2;
rep(i , 0 , n) S[i] = A[i] = A2[i];
sort(S , S + n);
m = unique(S , S + n) - S;
bfs(St + 1 , ans[0] , 1);
bfs(St + 1 , ans[1] , 2);
reverse(A , A + n);
St = n - 1 - St;
bfs(St + 1 , ans[2] , 1);
bfs(St + 1 , ans[3] , 2);
ll answer = 0;
rep(i , 0 , d + 1) {
smax(answer , ans[0][i] + ans[3][d - i]);
smax(answer , ans[1][i] + ans[2][d - i]);
if (i) {
smax(answer , ans[0][i - 1] + ans[3][d - i] + A[St]);
smax(answer , ans[1][i - 1] + ans[2][d - i] + A[St]);
}
}
return answer;
}
