#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 2;
int n, cnt[N], t[N * 4], ar[N];
long long sum[N * 4];
void update(int pos, int val, int v = 1, int tl = 1, int tr = N - 1){
if(tl == tr){
t[v] += val;
sum[v] += val * ar[tl];
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm){
update(pos, val, v << 1, tl, tm);
} else {
update(pos, val, (v << 1) | 1, tm + 1, tr);
}
t[v] = t[v << 1] + t[(v << 1) | 1];
sum[v] = sum[v << 1] + sum[(v << 1) | 1];
}
}
long long get(int x, int v = 1, int tl = 1, int tr = N - 1){
if(x <= 0 && t[v] <= 0) return 0;
if(t[v] <= x) return sum[v];
int tm = (tl + tr) >> 1;
int cn = t[(v << 1) | 1];
long long res = 0;
if(cn <= x){
res += sum[(v << 1) | 1] + get(x - cn, v << 1, tl, tm);
} else {
res += get(x, (v << 1) | 1, tm + 1, tr);
}
return res;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
n = N;
int fl = 1;
long long ans = 0;
for(int i = 0; i < n; i ++)
if(attraction[i] > 100) fl = 0;
if(!start && fl){
for(int i = 0; i < n; i ++){
cnt[attraction[i]] ++;
long long res = 0;
if(i < d){
int now = d - i;
for(int i = 100; i >= 0; i --){
if(now >= cnt[i]){
res += cnt[i] * i;
now -= cnt[i];
} else {
res += now * i;
now = 0;
}
}
}
ans = max(ans, res);
}
} else {
vector <int> v;
for(int i = 0; i < n; i ++)
v.push_back(attraction[i]);
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for(int i = 0; i < n; i ++){
attraction[i] = lower_bound(v.begin(), v.end(), attraction[i]) - v.begin() + 1;
}
for(int i = 1; i <= n; i ++)
ar[i] = v[i - 1];
for(int i = 0; i <= start; i ++){
int last;
for(int j = i; j < n; j ++){
update(attraction[j], 1);
last = j;
if(start <= j){
int ost = d - (min(j - start, start - i) + (j - i));
if(ost <= 0) break;
ans = max(ans, get(ost));
}
}
for(int j = i; j <= last; j ++){
update(attraction[j], -1);
}
}
}
return ans;
}
