//#include "grader.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct tree{
vector<ll> seg;
void init(ll n){
seg.resize(4*n+9);
}
void upd(ll v, ll tl, ll tr, ll idx, ll val){
if(tl == idx && tr == idx){
seg[v] += val;
return;
}
if(idx <= (tl+tr)/2)
upd(2*v, tl, (tl+tr)/2, idx, val);
else
upd(2*v+1, (tl+tr)/2+1, tr, idx, val);
seg[v] = seg[2*v]+seg[2*v+1];
}
pll get(ll v, ll tl, ll tr, ll val){
if(tl == tr)
return {tl, max(0LL, seg[v]-val)};
if(seg[2*v+1] >= val)
return get(2*v+1, (tl+tr)/2+1, tr, val);
else
return get(2*v, tl, (tl+tr)/2, val-seg[2*v+1]);
}
};
struct bit{
ll n;
vector<ll> bit;
void init(ll sz){
bit.resize(sz+1);
n = sz;
}
void upd(ll idx, ll val){
for(++idx; idx > 0; idx -= idx&(-idx))
bit[idx] += val;
}
ll get(ll idx){
ll ret = 0;
for(++idx; idx <= n; idx += idx&(-idx))
ret += bit[idx];
return ret;
}
};
vector<ll> mpp;
ll maxn;
ll get(ll x){
return lower_bound(all(mpp), x)-mpp.begin();
}
int N, D;
ll getval(vector<ll> v, ll lim){
tree s;
bit b;
s.init(maxn);
b.init(maxn);
ll ans = 0;
for(int i = 0; i < v.size(); ++i){
s.upd(1, 0, maxn-1, v[i], 1);
b.upd(v[i], mpp[v[i]]);
if(lim-i <= 0) break;
pll idx = s.get(1, 0, maxn-1, lim-i);
//cout << i << ' ' << mpp[idx.ff] << '\n';
ans = max(ans, b.get(idx.ff)-mpp[idx.ff]*idx.ss);
}
return ans;
}
vector<ll> getvec(vector<ll> v, ll come){
vector<ll> ret(D);
vector<ll> s;
for(ll i = 0; i < v.size(); ++i){
s.insert(lower_bound(all(s), v[i], greater<ll>()), v[i]);
ll cost = i;
if(come)
cost *= 2;
ll val = 0;
for(auto u : s){
++cost;
val += u;
if(cost >= D) break;
ret[cost] = max(ret[cost], val);
}
}
for(ll i = 1; i < ret.size(); ++i)
ret[i] = max(ret[i-1], ret[i]);
return ret;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n;
D = d;
for(int i = 0; i < n; ++i)
mpp.pb(attraction[i]);
sort(all(mpp));
mpp.resize(unique(all(mpp))-mpp.begin());
maxn = mpp.size();
for(int i = 0; i < n; ++i)
attraction[i] = get(attraction[i]);
if(start == 0){
vector<ll> v;
for(int i = 0; i < n; ++i)
v.pb(attraction[i]);
return getval(v, d);
}
vector<ll> v1, v2, v3, v4;
for(ll i = start; i < n; ++i)
v1.pb(mpp[attraction[i]]);
for(ll i = start+1; i < n; ++i)
v2.pb(mpp[attraction[i]]);
for(ll i = start; i >= 0; --i)
v3.pb(mpp[attraction[i]]);
for(ll i = start-1; i >= 0; --i)
v4.pb(mpp[attraction[i]]);
vector<ll> go1, come1, go2, come2;
go1 = getvec(v2, 0);
come1 = getvec(v1, 1);
go2 = getvec(v4, 0);
come2 = getvec(v3, 1);
ll ans = 0;
for(ll i = 0; i < d; ++i){
ans = max(ans, come1[i]+go2[d-i-1]);
ans = max(ans, come2[i]+go1[d-i-1]);
}
vector<ll> v;
for(int i = start; i < n; ++i)
v.pb(attraction[i]);
ans = max(ans, getval(v, d));
v.clear();
for(int i = start; i >= 0; --i)
v.pb(attraction[i]);
ans = max(ans, getval(v, d));
return ans;
}
