#include "holiday.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n;
int pos, d;
int a[MAXN];
llong ans;
std::multiset <int> s;
void insert(int val)
{
s.insert(val);
}
void erase(int val)
{
assert(s.count(val));
s.erase(s.find(val));
}
llong findSum(int k)
{
k = std::min(k, (int)s.size());
auto it = s.rbegin();
llong res = 0;
for (int i = 0 ; i < k ; ++i)
{
res += *it;
it++;
}
return res;
}
int moL = 1;
int moR = 0;
llong getCost(int l, int r)
{
while (moL > l) insert(a[--moL]);
while (moR < r) insert(a[++moR]);
while (moL < l) erase(a[moL++]);
while (moR > r) erase(a[moR--]);
return findSum(d - pos + 2 * l - r);
}
void rec(int l, int r, int optL, int optR)
{
if (d - pos + 2 * r - optL <= 0)
{
return;
}
int opt = -1;
int mid = (l + r) / 2;
llong currSum = 0;
llong currRes = 0;
for (int i = optL ; i <= optR && d - pos + 2 * mid - i > 0 ; ++i)
{
currSum = getCost(mid, i);
if (currSum > currRes)
{
opt = i;
currRes = currSum;
}
}
if (opt == -1)
{
opt = optL;
}
if (l < mid) rec(l, mid - 1, optL, opt);
if (mid < r) rec(mid + 1, r, opt, optR);
ans = std::max(ans, currRes);
}
llong findMaxAttraction(int N, int start, int D, int A[])
{
n = N;
d = D;
pos = start + 1;
for (int i = 1 ; i <= n ; ++i)
{
a[i] = A[i - 1];
}
if (pos <= n)
{
rec(1, pos, pos + 1, n);
}
std::reverse(a + 1, a + 1 + n);
pos = n - pos + 1;
s.clear();
moL = 1;
moR = 0;
if (pos <= n)
{
rec(1, pos, pos + 1, n);
}
return ans;
}
