#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
const int lim = 1e5 + 5;
int n, start, d, a[lim];
namespace sub13{
const int lim = 3e3 + 5;
ll bit_s[lim];
int bit_c[lim];
void update(int p, int x){
for(; p <= n; p += p & -p){
bit_s[p] += x;
bit_c[p]++;
}
}
ll solve(){
vector<int>coma(n + 1), ia(n);
iota(ia.begin(), ia.end(), 1);
sort(ia.begin(), ia.end(), [&] (int i, int j){
return a[i] > a[j];
});
for(int i = 0; i < n; i++){
coma[ia[i]] = i + 1;
}
ll ans = 0;
for(int l = 1; l <= start; l++){
memset(bit_s, 0, sizeof(bit_s));
memset(bit_c, 0, sizeof(bit_c));
for(int r = l; r <= n; r++){
update(coma[r], a[r]);
if(r >= start){
int remain = d - (r - l) - min(start - l, r - start);
if(remain > 0){
ll cur = 0;
for(int p = 0, bit = 11; bit > -1; bit--){
int np = p | (1 << bit);
if(np <= n && remain >= bit_c[np]){
remain -= bit_c[p = np];
cur += bit_s[p];
}
}
maximize(ans, cur);
}
else{
break;
}
}
}
}
return ans;
}
}
namespace sub2{
const int LIM = 105;
int cnt[LIM];
ll solve(){
memset(cnt, 0, sizeof(cnt));
int ans = 0;
for(int i = 1; i <= n; i++){
cnt[a[i]]++;
int remain = d - i + 1, cur = 0;
for(int j = LIM - 1; j > -1; j--){
int x = min(remain, cnt[j]);
cur += j * x;
remain -= x;
}
maximize(ans, cur);
}
return ans;
}
}
namespace sub4{
ll ans = 0;
int L, R, coma[lim];
ll bit_s[lim];
int bit_c[lim];
void add(int p, int x){
for(; p <= n; p += p & -p){
bit_s[p] += x;
bit_c[p]++;
}
}
void del(int p, int x){
for(; p <= n; p += p & -p){
bit_s[p] -= x;
bit_c[p]--;
}
}
ll query(int l, int r, int remain){
if(remain < 1){
return 0;
}
while(R < r){
R++;
add(coma[R], a[R]);
}
while(R > r){
del(coma[R], a[R]);
R--;
}
while(L < l){
del(coma[L], a[L]);
L++;
}
while(L > l){
L--;
add(coma[L], a[L]);
}
ll sum = 0;
for(int p = 0, bit = 17; bit > -1; bit--){
int np = p | (1 << bit);
if(np <= n && remain >= bit_c[np]){
remain -= bit_c[p = np];
sum += bit_s[p];
}
}
return sum;
}
void dnc(int l, int r, int opt_l, int opt_r){
if(l > r){
return;
}
int opt, m = (l + r) >> 1;
ll best = -1;
for(int i = opt_l; i <= opt_r; i++){
if(maximize(best, query(i, m, d - (m - i) - (start - i)))){
opt = i;
}
}
maximize(ans, best);
dnc(l, m - 1, opt_l, opt);
dnc(m + 1, r, opt, opt_r);
}
void work(){
vector<int>ia(n);
iota(ia.begin(), ia.end(), 1);
sort(ia.begin(), ia.end(), [&] (int i, int j){
return a[i] > a[j];
});
for(int i = R = 0; i < n; i++){
coma[ia[i]] = i + 1;
}
memset(bit_c, 0, sizeof(bit_c));
memset(bit_s, 0, sizeof(bit_s));
dnc(start, n, L = 1, start);
}
ll solve(){
work();
reverse(a + 1, a + n + 1);
start = n - start + 1;
work();
return ans;
}
}
ll findMaxAttraction(int _n, int _start, int _d, int _a[]){
n = _n;
start = _start + 1;
d = _d;
for(int i = 1; i <= n; i++){
a[i] = _a[i - 1];
}
if(n <= 3000){
return sub13::solve();
}
if(start == 1 && *max_element(a + 1, a + n + 1) <= 100){
return sub2::solve();
}
return sub4::solve();
}
