#include "holiday.h"
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn=1e5+5, Log=17, pot=(1<<Log);
ll t[pot*2];
int br[pot*2];
int niz[maxn];
int pos[maxn];
bool cmp(int a, int b){
return niz[a]>niz[b];
}
void update(int x){
x+=pot;
br[x]^=1;
for(x/=2; x>0; x/=2){
br[x]=br[x*2]+br[x*2+1];
t[x]=0;
if(br[x*2]){
t[x]+=t[x*2];
}
if(br[x*2+1]){
t[x]+=t[x*2+1];
}
}
}
ll query(int x, int broj){
// cout << x << ' ' << broj << endl;
if(broj<=0 || !br[x]){
return 0;
}
if(br[x]<=broj){
return t[x];
}
return query(x*2, broj)+query(x*2+1, broj-br[x*2]);
}
pair < int, ll > dp1[maxn*3];
pair < int, ll > dp2[maxn*3];
int pozicija[maxn];
int poc;
void rijesi1(int L, int D, int l, int d){
// cout << L << ' ' << D << ' ' << l << ' ' << d << endl;
if(l>=d){
return;
}
int mid=(l+d)/2;
ll maksi=0;
int ind=0;
ll val;
for(int i=L; i<D; i++){
update(pozicija[i]);
val=query(1, mid-(i-poc));
if(maksi<val){
maksi=val;
ind=i;
}
}
dp1[mid]={ind, maksi};
for(int i=L; i<D; i++){
update(pozicija[i]);
}
rijesi1(L, ind+1, l, mid);
for(int i=L; i<ind; i++){
update(pozicija[i]);
}
rijesi1(ind, D, mid+1, d);
for(int i=L; i<ind; i++){
update(pozicija[i]);
}
}
void rijesi2(int L, int D, int l, int d){
// cout << L << ' ' << D << ' ' << l << ' ' << d << endl;
if(l>=d){
return;
}
int mid=(l+d)/2;
ll maksi=0;
int ind=D-1;
ll val;
for(int i=D-1; i>=L; i--){
update(pozicija[i]);
val=query(1, mid-(poc-1-i));
// cout << val << endl;
if(maksi<val){
maksi=val;
ind=i;
}
}
// cout << mid << ' ' << ind << ' ' << maksi << endl;
// cout << "poso" << endl;
dp2[mid]={ind, maksi};
for(int i=L; i<D; i++){
update(pozicija[i]);
}
rijesi2(ind, D, l, mid);
for(int i=D-1; i>ind; i--){
update(pozicija[i]);
}
rijesi2(L, ind+1, mid+1, d);
for(int i=D-1; i>ind; i--){
update(pozicija[i]);
}
}
ll findMaxAttraction(int n, int x, int d, int l[]){
poc=x;
for(int i=0; i<n; i++){
niz[i]=l[i];
pos[i]=i;
}
sort(pos, pos+n, cmp);
for(int i=0; i<n; i++){
t[i+pot]=niz[pos[i]];
pozicija[pos[i]]=i;
}
rijesi1(x, n, 0, n*3);
rijesi2(0, x, 0, n*3);
int druga;
ll uk;
ll sol=0;
for(int i=0; i<=d; i++){
druga=max(0, d-i-(dp1[i].first-x+1));
uk=dp1[i].second+dp2[druga].second;
sol=max(sol, uk);
druga=max(0, d-i-(x-dp2[i].first+1));
uk=dp2[i].second+dp1[druga].second;
sol=max(sol, uk);
}
return sol;
}
