#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
long long dp[2][100005];
int pos[2][100005];
int a[100005];
int curl = 1, curr = 0;
vector<long long> com;
struct Node{
long long sum = 0;
int cnt = 0;
}t[400005];
void update(int v, int tl, int tr, int pos, int x){
if(tl == tr){
t[v].cnt += x;
t[v].sum += x*(com[tl-1]);
}else{
int tm = (tl+tr)/2;
if(pos <= tm) update(v*2,tl,tm,pos,x);
else update(v*2+1,tm+1,tr,pos,x);
t[v].cnt = t[v*2].cnt + t[v*2+1].cnt;
t[v].sum = t[v*2].sum + t[v*2+1].sum;
}
}
long long walk(int v, int tl, int tr, int k){
if(tl == tr) return min(k,t[v].cnt) * (com[tl-1]);
int tm = (tl+tr)/2;
if(k >= t[v*2+1].cnt) return walk(v*2,tl,tm,k-t[v*2+1].cnt) + t[v*2+1].sum;
return walk(v*2+1,tm+1,tr,k);
}
int query(int l, int r, int k){
while(curr < r) update(1,1,com.size(),a[++curr],1);
while(curr > r) update(1,1,com.size(),a[curr--],-1);
while(curl < l) update(1,1,com.size(),a[curl++],-1);
while(curl > l) update(1,1,com.size(),a[--curl],1);
return walk(1,1,com.size(),k);
}
void DnC(int a[], long long d[], int p[], int l, int r, int tl, int tr, int s){
if(tl > tr) return;
int tm = (tl+tr)/2;
for(int i = l; i <= min(tm+s,r); i++){
int val = query(s,i,tm-(i-s));
if(d[tm] < val){
d[tm] = val;
p[tm] = i;
}
}
//cout << tm << ' ' << l << ' ' << r << ' ' << query(s,l,tm) << ' ' << d[tm] << endl;
DnC(a,d,p,l,p[tm],tl,tm-1,s);
DnC(a,d,p,p[tm],r,tm+1,tr,s);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]){
start++;
for(int i = 1; i <= n; i++) com.push_back(attraction[i-1]);
sort(com.begin(), com.end());
com.erase(unique(com.begin(), com.end()), com.end());
for(int i = 1; i <= n; i++) attraction[i-1] = lower_bound(com.begin(), com.end(), attraction[i-1]) - com.begin() + 1;
for(int i = 1; i <= n; i++) a[i] = attraction[i-1];
DnC(a,dp[0],pos[0],start+1,n,1,d,start+1);
query(1,0,0);
for(int i = 1; i <= n; i++){
a[i] = attraction[n-i];
//cout << a[i] << endl;
}
DnC(a,dp[1],pos[1],n-start+2,n,1,d,n-start+2);
for(int i = 1; i <= n; i++) a[i] = attraction[i-1];
long long ans = max(dp[1][d], dp[1][d-1]+com[a[start]-1]);
//for(int i = 1; i <= d; i++) cout << dp[0][i] << ' ' << dp[1][i] << endl;
for(int i = 1; i <= d; i++){ //days used going right
if(d-i-(pos[0][i-1] - start)-1 > 0) ans = max(ans, dp[0][i-1] + dp[1][d-i-(pos[0][i-1] - start)-1]);
if(d-i-(pos[0][i-1] - start)-2 > 0) ans = max(ans, dp[0][i-1] + dp[1][d-i-(pos[0][i-1] - start)-2]+com[a[start]-1]);
}
return ans;
}
