#include <bits/stdc++.h>
#include "holiday.h"
#define N 100005
using namespace std;
typedef long long ll;
struct node {int l,r,v1;ll v2;};
int n,start,d,a[N],b[N],c,cn,root[N];
map<int,int> mp,to;
ll ans;
node tree[20*N];
void initseg(int nd,int l,int r)
{
tree[nd].v1=tree[nd].v2=0;
if(l==r)return;
tree[nd].l=++cn;
tree[nd].r=++cn;
int m=(l+r)/2;
initseg(tree[nd].l,l,m);
initseg(tree[nd].r,m+1,r);
}
void add(int ln,int rn,int l,int r,ll v1,ll v2)
{
tree[rn].v1=tree[ln].v1+1;
tree[rn].v2=tree[ln].v2+v2;
if(l==r)return;
int m=(l+r)/2;
if(v1<=m){
tree[rn].r=tree[ln].r;
tree[rn].l=++cn;
add(tree[ln].l,tree[rn].l,l,m,v1,v2);
}
else{
tree[rn].l=tree[ln].l;
tree[rn].r=++cn;
add(tree[ln].r,tree[rn].r,m+1,r,v1,v2);
}
}
ll query(int ln,int rn,int l,int r,ll k)
{
if(k<=0) return 0;
if(l==r){
if(k<=tree[rn].v1-tree[ln].v1)
return (tree[rn].v2-tree[ln].v2)/(tree[rn].v1-tree[ln].v1)*k;
return tree[rn].v2-tree[ln].v2;
}
int m=(l+r)/2;
ll use=tree[tree[rn].r].v1-tree[tree[ln].r].v1;
if(use>k)
return query(tree[ln].r,tree[rn].r,m+1,r,k);
else
return tree[tree[rn].r].v2-tree[tree[ln].r].v2+query(tree[ln].l,tree[rn].l,l,m,k-use);
}
void dnc(int s,int e,int l,int r)
{
if(s>e||l>r)return;
int m=(s+e)/2,bestl=r,bestr=l;
ll cans=-1,curr;
for(int i=l;i<=r;i++){
curr=query(root[m-1],root[i],1,c,d-i+m-min(start-m,i-start));
if(curr<=0)break;
if(curr>cans){
cans=curr;
bestl=bestr=i;
}
else if(curr==cans){
bestl=min(bestl,i);
bestr=max(bestr,i);
}
}
ans=max(ans,cans);
dnc(s,m-1,l,bestr);
dnc(m+1,e,bestl,r);
}
ll findMaxAttraction(int n_,int start_,int d_,int attraction[])
{
n=n_;
start=start_;
d=d_;
for(int i=0;i<n;i++){
a[i]=attraction[i];
mp[a[i]]++;
}
for(auto &it : mp)
to[it.first]=++c;
root[0]=++cn;
initseg(root[0],1,c);
for(int i=1;i<=n;i++){
root[i]=++cn;
add(root[i-1],root[i],1,c,to[attraction[i-1]],attraction[i-1]);
}
start++;
dnc(1,start,start,n);
return ans;
}
