#include<bits/stdc++.h>
#include"holiday.h"
#define MAXN 500007
using namespace std;
int n,a[MAXN];
vector<int> w;
unordered_map<int,int> mp;
int ret[MAXN],cnt;
long long ans;
struct ST{
pair<long long,int> tree[4*MAXN];
void init(){
for(int i=1;i<=4*cnt;i++){
tree[i]={0,0};
}
}
pair<long long,int> combine(pair<long long,int> fr,pair<long long,int> sc){
return {fr.first+sc.first,fr.second+sc.second};
}
void update(int v,int l,int r,int pos){
if(l==r){
tree[v].second++;
tree[v].first+=ret[l];
}else{
int tt=(l+r)/2;
if(pos<=tt)update(2*v,l,tt,pos);
else update(2*v+1,tt+1,r,pos);
tree[v]=combine(tree[2*v],tree[2*v+1]);
}
}
long long getsum(int v,int l,int r,long long k){
if(l==r){
if(tree[v].second<=k)return tree[v].first;
return k*ret[l];
}else{
int tt=(l+r)/2;
if(tree[2*v+1].second>=k){
return getsum(2*v+1,tt+1,r,k);
}else{
return getsum(2*v,l,tt,k-tree[2*v+1].second) + tree[2*v+1].first;
}
}
}
}seg;
long long solve(int pos,int days){
if(days<=0)return 0;
long long res=0;
seg.init();
for(int i=pos;i<=n;i++){
seg.update(1,1,cnt,a[i]);
if(days-(i-pos)<=0)break;
res=max(res,seg.getsum(1,1,cnt,days-(i-pos)));
}
return res;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
//long long int findMaxAttraction(int N, int start, int d, vector<int> attraction) {
n=N; start++;
for(int i=1;i<=n;i++){
a[i]=attraction[i-1];
w.push_back(a[i]);
}
sort(w.begin(),w.end());
for(int i=0;i<w.size();i++){
if(i==0 or w[i]!=w[i-1])cnt++;
mp[w[i]]=cnt; ret[cnt]=w[i];
}
for(int i=1;i<=n;i++)a[i]=mp[a[i]];
for(int i=start;i>=1;i--){
ans=max(ans,solve(i,d-(start-i)));
}
if(start!=1){
reverse(a+1,a+n+1);
start=n-start+1;
for(int i=start;i>=1;i--){
ans=max(ans,solve(i,d-(start-i)));
}
}
return ans;
}
/*int main(){
cout<<findMaxAttraction(5,2,7,{10,2,20,30,1})<<"\n";
return 0;
}*/
