#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
const int maxn = 2e5 + 3;
int n;
int idx[maxn], val[maxn];
pair <long long, int> tr[maxn * 4];
void merge(int v)
{
tr[v].first = tr[v * 2].first + tr[v * 2 + 1].first;
tr[v].second = tr[v * 2].second + tr[v * 2 + 1].second;
}
void turn_on(int v, int l, int r, int pos)
{
if (l == r)
{
tr[v] = {val[pos], 1};
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
turn_on(v * 2, l, mid, pos);
else
turn_on(v * 2 + 1, mid + 1, r, pos);
merge(v);
}
void turn_off(int v, int l, int r, int pos)
{
if (l == r)
{
tr[v] = {0, 0};
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
turn_off(v * 2, l, mid, pos);
else
turn_off(v * 2 + 1, mid + 1, r, pos);
merge(v);
}
long long get(int v, int l, int r, int k)
{
if (k <= 0)
return 0;
if (l == r)
return tr[v].first;
int mid = (l + r) / 2;
if (tr[v * 2 + 1].second > k)
return get(v * 2 + 1, mid + 1, r, k);
else
return tr[v * 2 + 1].first + get(v * 2, l, mid, k - tr[v * 2 + 1].second);
}
pair <long long, int> f1[maxn], f2[maxn], f3[maxn], f4[maxn];
void calc1(int l, int r, int opt_l, int opt_r, int start)
{
if (l > r || opt_l > opt_r)
return;
int mid = (l + r) / 2;
long long best = 0;
int idx_best = -1;
for (int i = opt_l; i <= opt_r; i++)
{
turn_on(1, 0, n-1, idx[i]);
long long curr_val = get(1, 0, n-1, max(0, mid - (i - start)));
if (curr_val > best)
best = curr_val, idx_best = i;
}
f1[mid] = {best, idx_best};
for (int i = opt_l; i <= opt_r; i++)
turn_off(1, 0, n-1, idx[i]);
calc1(l, mid-1, opt_l, idx_best, start);
for (int i = opt_l; i < idx_best; i++)
turn_on(1, 0, n-1, idx[i]);
calc1(mid+1, r, idx_best, opt_r, start);
for (int i = opt_l; i < idx_best; i++)
turn_off(1, 0, n-1, idx[i]);
}
void calc2(int l, int r, int opt_l, int opt_r, int start)
{
if (l > r || opt_l > opt_r)
return;
int mid = (l + r) / 2;
long long best = 0;
int idx_best = -1;
for (int i = opt_r; i >= opt_l; i--)
{
turn_on(1, 0, n-1, idx[i]);
long long curr_val = get(1, 0, n-1, max(0, mid - (start - i)));
if (curr_val > best)
best = curr_val, idx_best = i;
}
f2[mid] = {best, idx_best};
for (int i = opt_l; i <= opt_r; i++)
turn_off(1, 0, n-1, idx[i]);
calc2(l, mid-1, idx_best, opt_r, start);
for (int i = opt_r; i > idx_best; i--)
turn_on(1, 0, n-1, idx[i]);
calc2(mid+1, r, opt_l, idx_best, start);
for (int i = opt_r; i > idx_best; i--)
turn_off(1, 0, n-1, idx[i]);
}
void calc3(int l, int r, int opt_l, int opt_r, int start)
{
if (l > r || opt_l > opt_r)
return;
int mid = (l + r) / 2;
long long best = 0;
int idx_best = -1;
for (int i = opt_l; i <= opt_r; i++)
{
turn_on(1, 0, n-1, idx[i]);
long long curr_val = get(1, 0, n-1, max(0, mid - (i - start)));
if (curr_val > best)
best = curr_val, idx_best = i;
}
f3[mid] = {best, idx_best};
for (int i = opt_l; i <= opt_r; i++)
turn_off(1, 0, n-1, idx[i]);
calc3(l, mid-1, opt_l, idx_best, start);
for (int i = opt_l; i < idx_best; i++)
turn_on(1, 0, n-1, idx[i]);
calc3(mid+1, r, idx_best, opt_r, start);
for (int i = opt_l; i < idx_best; i++)
turn_off(1, 0, n-1, idx[i]);
}
void calc4(int l, int r, int opt_l, int opt_r, int start)
{
if (l > r || opt_l > opt_r)
return;
int mid = (l + r) / 2;
long long best = 0;
int idx_best = -1;
for (int i = opt_r; i >= opt_l; i--)
{
turn_on(1, 0, n-1, idx[i]);
long long curr_val = get(1, 0, n-1, max(0, mid - (start - i)));
if (curr_val > best)
best = curr_val, idx_best = i;
}
f4[mid] = {best, idx_best};
for (int i = opt_l; i <= opt_r; i++)
turn_off(1, 0, n-1, idx[i]);
calc4(l, mid-1, idx_best, opt_r, start);
for (int i = opt_r; i > idx_best; i--)
turn_on(1, 0, n-1, idx[i]);
calc4(mid+1, r, opt_l, idx_best, start);
for (int i = opt_r; i > idx_best; i--)
turn_off(1, 0, n-1, idx[i]);
}
long long findMaxAttraction(int _n, int start, int d, int attraction[])
{
n = _n;
vector <pair <int, int> > temp;
for (int i = 0; i < n; i++)
temp.push_back({attraction[i], i});
sort (temp.begin(), temp.end());
for (int i = 0; i < n; i++)
{
idx[temp[i].second] = i;
val[i] = temp[i].first;
}
//calc1(1, d, start, n-1, start);
//calc2(1, d, 0, start-1, start-1);
//calc3(1, d, start+1, n-1, start+1);
//calc4(1, d, 0, start, start);
/*
long long ans = 0;
for (int i = 1; i <= d; i++)
ans = max(ans, f1[i].first + f2[max(0, d-i-(f1[i].second-start)-1)].first);
for (int i = 1; i <= d; i++)
ans = max(ans, f4[i].first + f3[max(0, d-i-(start-f4[i].second)-1)].first);
*/
for (int i = 0; i < n; i++)
{
turn_on(1, 0, n-1, idx[i]);
f1[d].first = max(f1[d].first, get(1, 0, n-1, d - i));
}
return f1[d].first;
}
/*
int m, start, d, a[maxn];
int main()
{
cin >> m >> start >> d;
for (int i = 0; i < m; i++)
cin >> a[i];
cout << findMaxAttraction(m, start, d, a) << endl;
}
*/
