#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5+10;
const int INF = 1e9;
typedef pair<ll,ll> pii;
int val[MAXN];
struct node {
int l, r, mid; ll sum, cnt;
node *le, *ri;
void bd(int l2, int r2){
l = l2; r = r2; mid = (l+r)/2;
sum = 0; cnt = 0;
if(l==r) return;
le = new node(); le->bd(l, mid);
ri = new node(); ri->bd(mid+1, r);
}
ll que(int w){
if(w<=0) return 0;
if(cnt <= w) return sum;
if(l == r) return 1ll*val[l]*w;
if(ri->cnt >= w) return ri->que(w);
return le->que(w - ri->cnt) + ri->que(ri->cnt);
}
pii upd(int x, int p){
if(r<x || x<l) return {sum, cnt};
if(l==r && l==x){
sum += 1ll*val[x]*p; cnt += p;
return {sum, cnt};
}
pii lupd = le->upd(x, p); pii rupd = ri->upd(x, p);
sum = lupd.fi + rupd.fi; cnt = lupd.se + rupd.se;
return {sum, cnt};
}
} A;
int n, sta, d;
int a[MAXN];
map<int,int> idx;
ll ret = 0;
int le = 1, ri = 0;
void setlr(int l,int r){
while(le < l){
A.upd(idx[a[le++]], -1);
} //mid-1, out
while(le > l){
A.upd(idx[a[--le]], 1);
} //mid, in
while(ri < r){
A.upd(idx[a[++ri]], 1);
} //optl, in
while(ri > r){
A.upd(idx[a[ri--]], -1);
} //optr+1, out
}
void solve(int l, int r, int optl, int optr){
if(l > r) return;
int mid = (l+r)/2, opt;
ll dp = -INF; //cari value mid
// mid - le udh ke build
if(ri-optl <= optr-ri){
for(int i=optl; i<=optr; i++){
setlr(mid,i);
// mid - i
// d-(sta-mid)-(i-mid)
ll can = A.que(d-sta + 2*mid - i);
//cout << mid << ' ' << i << ' ' << can << "que\n";
if(dp < can){
dp = can;
opt = i;
}
}
solve(mid+1, r, opt, optr); solve(l, mid-1, optl, opt);
} else {
for(int i=optr; i>=optl; i--){
setlr(mid,i);
ll can = A.que(d-sta + 2*mid - i);
//cout << mid << ' ' << i << ' ' << can << "que\n";
if(dp <= can){
dp = can;
opt = i;
}
}
solve(l, mid-1, optl, opt); solve(mid+1, r, opt, optr);
}
//cout << mid << ' '<< opt << ' ' << dp << "dp\n";
ret = max(ret, dp);
}
long long int findMaxAttraction(int N, int start, int D, int X[]) {
n = N; sta = start; d = D;
sta++;
set <int> s;
for(int i=0; i<=n-1; i++){
a[i+1] = X[i];
s.insert(a[i+1]);
}
int index = 0;
for(auto in : s){
idx[in] = ++index;
val[index] = in;
//cout << in << ' ' << index << "ind\n";
}
//cout << "\nA\n";
le = sta; ri = sta-1;
A.bd(1, MAXN);
solve(1, sta, sta, n);
for(int i=1; i<n-i+1; i++) swap(a[i], a[n-i+1]);
sta = n-sta+1;
//cout << "\nB\n";
le = sta; ri = sta-1;
A.bd(1, MAXN);
solve(1, sta, sta, n);
return ret;
}
