#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define left h*2,l,(l +r)/2
#define right h*2+1,(l + r)/2 + 1,r
using namespace std;
const int N = 2e5 + 3;
ll ans = 0,arr[N];
int id,D,rev[N],L,R,n;
map <int,int> mp;
vector <int> vec;
pair <ll,ll> t[4*N];
void upd(int h,int l,int r,int idx,int val){
if (l == r){
t[h].f += val * rev[l];
t[h].s += val;
return;
}
if (idx > (l + r)/2) upd(right,idx,val);
else upd(left,idx,val);
t[h].f = t[h*2].f + t[h*2+1].f;
t[h].s = t[h*2].s + t[h*2+1].s;
}
ll get(int h,int l,int r,int k){
if (l == r) {
ll vl = t[h].f / t[h].s;
return vl * k;
}
if (t[h*2 + 1].s >= k) return get(right,k);
return t[h*2 + 1].f + get(left,k - t[h*2+ 1].s);
}
void add(int i){
upd(1,1,n,arr[i],+1);
}
void del(int i){
upd(1,1,n,arr[i],-1);
}
void mo(int l,int r){
while (L > l) add(--L);
while (R < r) add(++R);
while (L < l) del(L++);
while (R > r) del(R--);
}
void go(int l1,int r1,int l2,int r2){
if (l1 > r1) return;
if (l1 > id) return;
int mid = (l1 + r1)/2,opt = 0;
ll mx = -1;
for (int i = l2; i <= r2; i++){
int l = mid,r = i;
l = min(l,id);
r = max(r,id);
mo(l,r);
int len = r - l + min(r - id,id - l);
int cnt = D - len;
cnt = min(cnt,r-l+1);
ll cur = 0;
if (cnt >= t[1].s) cur = t[1].f;
else if (cnt > 0) cur = get(1,1,n,cnt);
if (cur > mx){
mx = cur;
opt = i;
}
}
ans=max(ans,mx);
go(l1,mid-1,l2,opt);
go(mid+1,r1,opt,r2);
}
long long int findMaxAttraction(int m, int start, int d, int attraction[]) {
n = m;
D = d;
for (int i=0;i<n;i++)
arr[i]=attraction[i],vec.push_back(arr[i]);
sort(vec.begin(),vec.end());
int val=0;
for (int i=0;i<vec.size();i++){
if(!i || vec[i] != vec[i - 1]) ++val;
mp[vec[i]] = val;
rev[val] = vec[i];
}
for (int i=0;i<n;i++)
arr[i] = mp[arr[i]];
L = 0; R = -1;
id = start;
go(0,n - 1,0,n - 1);
return ans;
}
