#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include"holiday.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 666013;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;
ll v[NMAX];
ll N;
ll c;
ll D;
ll fdr[NMAX];
ll fst[NMAX];
map <ll, ll> mp;
pii normalizare[NMAX];
class Fenwick{
ll aib[NMAX];
public:
void init(){
for(int i = 0; i < NMAX; i++)
aib[i] = 0;
}
void update(ll node, ll x){
for(ll i = node; i <= N; i += i&(-i))
aib[i] += x;
}
ll query(ll node){
ll x = 0;
for(ll i = node; i > 0; i -= i&(-i))
x += aib[i];
return x;
}
ll kth(ll node){
ll idx = 0;
for(ll i = nr_of_bits; i >= 0; i--){
ll nxt = idx | (1 << i);
if(nxt <= N && aib[nxt] <= node){
idx = nxt;
node -= aib[nxt];
}
}
return idx;
}
};
class Structura{
Fenwick cnt, suma;
public:
void init(){
cnt.init();
suma.init();
}
ll scor(ll p){
ll poz = cnt.kth(p);
return suma.query(poz);
}
void insert(pii x){
ll poz = mp[x.second];
cnt.update(poz, 1);
suma.update(poz, x.first);
}
void erase(pii x){
ll poz = mp[x.second];
cnt.update(poz, -1);
suma.update(poz, -x.first);
}
int size(){
return suma.query(NMAX - 2);
}
}ura;
void calcdr(ll st, ll dr, ll l, ll r){
if(st > dr)
return;
ll target = (st + dr) / 2;
ll pz = 0, maxim = 0;
for(ll i = l; i <= r; i++){
ura.insert({v[i], i});
ll ramase = target - (i - c);
ll scor = ura.scor(ramase);
if(maxim < scor){
maxim = scor;
pz = i;
}
}
fdr[target] = maxim;
for(ll i = r; i >= pz; i--){
ura.erase({v[i], i});
}
calcdr(target + 1, dr, pz, r);
for(ll i = l; i < pz; i++){
ura.erase({v[i], i});
}
calcdr(st, target - 1, l, pz);
}
void calcst(ll st, ll dr, ll l, ll r){
if(st > dr){
return;
}
ll target = (st + dr) / 2;
ll pz = 0, maxim = 0;
for(ll i = r; i >= l; i--){
ura.insert({v[i], i});
ll ramase = target - (c - 1 - i) * 2;
ll scor = ura.scor(ramase);
if(maxim < scor){
maxim = scor;
pz = i;
}
}
fst[target] = maxim;
for(ll i = r; i >= l; i--){
ura.erase({v[i], i});
}
calcst(st, target - 1, pz, r);
for(ll i = pz + 1; i <= r; i++){
ura.insert({v[i], i});
}
calcst(target + 1, dr, l, pz);
for(ll i = pz + 1; i <= r; i++){
ura.erase({v[i], i});
}
}
ll solve(){
ura.init();
if(c != 0)
calcst(0, D, 0, c - 1); ura.init();
calcdr(0, D, c, N - 1);
ll maxim = 0;
for(ll i = 0; i <= D; i++){
if(D - i - 2 >= 0){
maxim = max(maxim, fdr[i] + fst[D - i - 2]);
}
maxim = max(maxim, fdr[i]);
maxim = max(maxim, fst[i]);
}
for(ll i = 0; i <= D; i++){
fst[i] = fdr[i] = 0;
}
return maxim;
}
bool cmp(pii a, pii b){
if(a.first != b.first){
return a.first > b.first;
}
return a.second < b.second;
}
bool ccmp(pii a, pii b){
if(a.first != b.first){
return a.first > b.first;
}
return a.second > b.second;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
c = start;
N = n;
D = d;
for(ll i = 0; i < n; i++){
v[i] = attraction[i];
normalizare[i + 1] = {v[i], i};
}
sort(normalizare + 1, normalizare + n + 1, cmp);
for(ll i = 1; i <= n; i++){
mp[normalizare[i].second] = i;
}
ll maxim = solve();
//debug(ura.size());
c = n - start - 1;
reverse(attraction, attraction + n);
for(ll i = 0; i < n; i++){
v[i] = attraction[i];
//debug(attraction[i]);
normalizare[i + 1] = {v[i], i};
}
sort(normalizare + 1, normalizare + n + 1, ccmp);
for(ll i = 1; i <= n; i++){
mp[normalizare[i].second] = i;
}
c = n - start - 1;
maxim = max(maxim, solve());
return maxim;
}
