#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
int n, S, D, mxv, dp[maxn], a[maxn], trq[4*maxn], trs[4*maxn], ccval[4*maxn];
void att(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
trq[no]+= val;
trs[no]+= val*ccval[l];
return;
}
int f1=2*no,f2=2*no+1,mid=(l+r)>>1;
att(f1,l,mid,pos,val);
att(f2,mid+1,r,pos,val);
trq[no] = trq[f1]+trq[f2];
trs[no] = trs[f1]+trs[f2];
}
int find(int no, int l, int r, int val) {
if(l == r) {
return ccval[l]*val;
}
int f1 = 2*no;
int f2 = 2*no+1;
int mid = (l+r)/2;
//tenta ir para esquerda e pegar a direita
if(val-trq[f2] > 0) return trs[f2] + find(f1,l,mid,val-trq[f2]);
else return find(f2,mid+1,r,val);
}
int L,R;
void sol(int l, int r, int opl, int opr) {
if(l > r) return;
int i = (l+r)/2;
//coloca o L no mid e o R no opl-1
while(L < i) {
att(1,1,mxv,a[L],-1);
L++;
}
while(L > i) {
L--;
att(1,1,mxv,a[L],+1);
}
while(R > opl) {
att(1,1,mxv,a[R],-1);
R--;
}
while(R < opl) {
R++;
att(1,1,mxv,a[R],+1);
}
int opi = -1;
for(int j = opl; j <= opr; j++) {
if(j != opl) {
R++;
att(1,1,mxv,a[R],+1);
}
int q = max(D-S+2*i-j,D-2*j+S+i);
q = min(q,j-i+1);
int val = find(1,1,mxv,q);
if(val > dp[i]) {
dp[i] = val;
opi = j;
}
}
sol(l,i-1,opl,opi);
sol(i+1,r,opi,opr);
}
int findMaxAttraction(int32_t N, int32_t start, int32_t d, int32_t attraction[]) {
n = N;
D = d;
S = start;
vector<int> cc;
for(int i = 0; i < n; i++) {
a[i] = attraction[i];
cc.pb(a[i]);
}
sort(all(cc));
cc.erase(unique(all(cc)),cc.end());
mxv = cc.size();
for(int i = 0; i < n; i++) {
dp[i] = -inf;
int aux = a[i];
a[i] = upper_bound(all(cc),a[i]) - cc.begin();
ccval[a[i]] = aux;
}
L = S;
R = S-1;
sol(0,S,S,n-1);
int ans = 0;
for(int i = 0; i < n; i++) {
ans = max(ans,dp[i]);
}
return ans;
}
