#include"holiday.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int MAX = 101010;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;
// ans[i] : i번째 도시를 마지막으로 할 때 최대 방문 개수
struct Node {
int l = 0, r = 0, c = 0; ll val = 0;
};
Node tree[60*MAX];
vector <int> num;
int st, d, root[MAX], sz, n;
ll ans;
void expand_tree(int s, int e, int k, int pnd, int cnd) {
if(s == e) {
tree[cnd].c = tree[pnd].c + 1;
tree[cnd].val = tree[pnd].val + num[k];
return;
}
int m = s + e >> 1;
if(k <= m) {
tree[cnd].r = tree[pnd].r;
tree[cnd].l = ++sz;
expand_tree(s, m, k, tree[pnd].l, tree[cnd].l);
}
else {
tree[cnd].l = tree[pnd].l;
tree[cnd].r = ++sz;
expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r);
}
tree[cnd].c = tree[tree[cnd].l].c + tree[tree[cnd].r].c;
tree[cnd].val = tree[tree[cnd].l].val + tree[tree[cnd].r].val;
}
ll cal(int s, int e, int cnt, int pnd, int cnd) {
if(s == e) return cnt * num[s];
int m = s + e >> 1, rcnt = tree[tree[cnd].r].c;
if(rcnt <= cnt) return cal(m+1, e, cnt, tree[pnd].r, tree[cnd].r);
else {
ll rval = tree[tree[cnd].r].val - tree[tree[pnd].r].val;
return cal(s, m, rcnt-cnt, tree[pnd].l, tree[cnd].l) + rval;
}
}
void dnc(int s, int e, int l, int r) {
if(s > e) return;
int m = (s + e) >> 1;
ll tans = 0, temp;
int idx = l, cnt;
for(int i = l; i <= r; i++) {
if(m < st) {
cnt = min(i - m + 1, d - (i - m) - (i - st));
if(cnt < 0) continue;
temp = cal(0, n-1, cnt, root[i], root[m-1]);
if(temp >= tans) {
idx = i;
tans = temp;
}
}
}
ans = max(ans, tans);
dnc(s, m-1, l, idx);
dnc(m+1, e, idx, r);
}
ll findMaxAttraction(int N, int start, int day, int arr[]) {
st = start + 1, d = day, n = N;
for(int i = 0; i < n; i++) {
num.eb(arr[i]);
}
sort(all(num));
for(int i = 0; i < n; i++) {
root[i+1] = ++sz;
int k = lower_bound(all(num), arr[i]) - num.begin();
expand_tree(0, n-1, k, root[i], root[i+1]);
}
dnc(1, st-1, st, n);
dnc(st+1, n, 1, st);
return ans;
}
