#include "holiday.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
template<typename T>
class PST
{
struct Node
{
int lidx, ridx;
T value;
Node() :value(T()), lidx(-1), ridx(-1) {}
};
public:
class iterator
{
public:
iterator(PST<T>& p, int n)
: pst(p), node(n) {}
iterator& operator=(const iterator& other)
{
assert(&pst == &other.pst);
node = other.node;
return *this;
}
T get() const
{
return pst.node[node].value;
}
iterator left() const
{
return iterator(pst, pst.node[node].lidx);
}
iterator right() const
{
return iterator(pst, pst.node[node].ridx);
}
private:
PST<T>& pst;
int node;
};
template<typename M>
PST(int n_, const M& m) : n(n_), merge(m) {}
iterator it(int r)
{
return iterator(*this, root[r]);
}
int rmost() const
{
return n;
}
int update(int idx, const T& value)
{
return update((int)root.size() - 1, idx, value);
}
int update(int pre, int idx, const T& value)
{
root.emplace_back(_update(root[pre], idx, value, 0, n));
return (int)root.size() - 1;
}
T query(int k, int start, int end)
{
return _query(root[k], start, end, 0, n);
}
void init()
{
root.push_back(init(0, n));
}
private:
int init(int start, int end)
{
int idx = node.size();
node.emplace_back();
if (start != end)
{
int mid = (start + end) / 2;
node[idx].lidx = init(start, mid);
node[idx].ridx = init(mid + 1, end);
}
return idx;
}
int _update(int prev, int idx, const T& value, int start, int end)
{
if (idx < start || idx > end)
return prev;
int nidx = node.size();
node.emplace_back();
if (start == end)
node[nidx].value = value;
else
{
int mid = (start + end) / 2;
node[nidx].lidx = _update(node[prev].lidx, idx, value, start, mid);
node[nidx].ridx = _update(node[prev].ridx, idx, value, mid + 1, end);
node[nidx].value = merge(node[node[nidx].lidx].value, node[node[nidx].ridx].value);
}
return nidx;
}
T _query(int idx, int start, int end, int left, int right)
{
if (start <= left && right <= end)
return node[idx].value;
int mid = (left + right) / 2;
if (mid + 1 > end)
return _query(node[idx].lidx, start, end, left, mid);
if (mid < start)
return _query(node[idx].ridx, start, end, mid + 1, right);
return merge(_query(node[idx].lidx, start, end, left, mid),
_query(node[idx].ridx, start, end, mid + 1, right));
}
using Merge = function<T(const T&, const T&)>;
Merge merge;
vector<int> root;
vector<Node> node;
int n;
};
int n, s, d;
auto tree = PST<ii64>(100005, [](const ii64& l, const ii64& r) { return ii64(l.xx + r.xx, l.yy + r.yy); });
vector<i64> arr;
i64 get(int l, int r)
{
int cnt = min(r - l + 1, d + 2 * l - r - s);
if (cnt <= 0)
return 0;
i64 res = 0;
auto lx = tree.it(l - 1);
auto rx = tree.it(r);
int s = 0, e = 100005;
int need = cnt;
while (need > 0)
{
if (s == e)
{
res += rx.get().xx - lx.get().xx;
break;
}
int m = (s + e) / 2;
auto lr = lx.right();
auto rr = rx.right();
if (rr.get().yy - lr.get().yy >= need)
{
lx = lr;
rx = rr;
s = m + 1;
continue;
}
need -= rr.get().yy - lr.get().yy;
res += rr.get().xx - lr.get().xx;
lx = lx.left();
rx = rx.left();
e = m;
}
return res;
}
i64 big[200005];
void f(int y1, int y2, int x1, int x2)
{
if (y1 > y2 || x1 > x2)
return;
i64 ans = -(1ll << 60);
i64 ansp = x1;
int y = (y1 + y2) / 2;
for (int i = x1; i <= x2; i++)
{
i64 v = get(y, i);
if (v > ans)
{
ans = v;
ansp = i;
}
}
big[y] = ans;
f(y1, y - 1, x1, ansp);
f(y + 1, y2, ansp, x2);
}
i64 solve()
{
for (int i = 0; i < n; i++)
big[i] = -(1ll << 60);
vector<ii64> byVal;
for (int i = 0; i < n; i++)
byVal.emplace_back(arr[i], i);
sort(all(byVal));
vector<int> order(n);
for (int i = 0; i < n; i++)
order[byVal[i].yy] = i + 1;
tree = PST<ii64>(100005, [](const ii64& l, const ii64& r) { return ii64(l.xx + r.xx, l.yy + r.yy); });
tree.init();
for (int i = 0; i < n; i++)
tree.update(order[i], ii64(arr[i], 1));
f(1, s, 1, n);
i64 ans = big[1];
for (int i = 1; i <= n; i++)
ans = max(ans, big[i]);
return ans;
}
long long int findMaxAttraction(int n_, int s_, int d_, int attraction[])
{
n = n_;
s = s_ + 1;
d = d_;
arr.resize(n);
for (int i = 0; i < n; i++)
arr[i] = attraction[i];
i64 ans = solve();
reverse(all(arr));
s = n + 1 - s;
i64 ans2 = solve();
return max(ans, ans2);
}
