#include <iostream>
#include <algorithm>
#include"holiday.h"
using namespace std;
using llong = long long;
#define BUGO(x) cerr << #x << ": " << x << '\n';
const int pool = 1000'000;
int nodes = 1;
int lson[pool], rson[pool], cnt[pool];
llong sum[pool];
int cnt2[101];
void Upd(int v, int vl, int vr, int i, bool add)
{
if (i <= 100)
{
if (add) ++cnt2[i];
else --cnt2[i];
}
if (vl == vr)
{
if (add)
sum[v] += i, ++cnt[v];
else
sum[v] -= i, --cnt[v];
return;
}
if (lson[v] == -1)
{
lson[v] = ++nodes;
rson[v] = ++nodes;
}
int vm = vl + (vr - vl) / 2;
if (i <= vm)
Upd(lson[v], vl, vm, i, add);
else
Upd(rson[v], vm + 1, vr, i, add);
sum[v] = sum[lson[v]] + sum[rson[v]];
cnt[v] = cnt[lson[v]] + cnt[rson[v]];
}
llong Get(int v, int vl, int vr, int x)
{
if (x == 0) return 0;
if (cnt[v] <= x) return sum[v];
int vm = vl + (vr - vl) / 2;
if (cnt[rson[v]] >= x)
return Get(rson[v], vm + 1, vr, x);
return Get(lson[v], vl, vm, x - cnt[rson[v]]) + sum[rson[v]];
}
long long int findMaxAttraction(int n, int start, int d, int a[]) {
fill(lson, lson + pool, -1);
fill(rson, rson + pool, -1);
int maxA = (n <= 3000 ? 1000'000'000 : 100);
llong ans = 0;
for (int l = start; l >= 0; --l)
{
Upd(1, 0, maxA, a[l], true);
for (int r = start; r < n; ++r)
{
if (r > start)
Upd(1, 0, maxA, a[r], true);
int move = start - l + r - start + min(start - l, r - start);
if (d - move > 0)
{
if (maxA == 100)
{
llong cur = 0;
int lft = d - move;
for (int i = 100; i >= 1; --i)
if (cnt2[i] >= lft) {
cur += lft * i;
break;
}
else {
cur += cnt2[i] * i;
lft -= cnt2[i];
}
ans = max(ans, cur);
}
else
ans = max(ans, Get(1, 0, maxA, d - move));
}
}
for (int r = start; r < n; ++r)
if (r > start)
Upd(1, 0, maxA, a[r], false);
}
return ans;
}
