#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct pair_hash{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
const int BASE = (1 << 18);
pair<int, ll> tree[2 * BASE + 7];
vi id;
vll A;
void upd(int ind, int ch, ll val){
ind += BASE;
while(ind > 0){
tree[ind].fi += ch;
tree[ind].se += (ch * val);
ind /= 2;
}
}
ll findSum(int v, int k){
if(k == 0){
return 0LL;
}
if(tree[v].fi == k){
return tree[v].se;
}
if(k <= tree[2 * v + 1].fi){
return findSum(2 * v + 1, k);
}
return findSum(2 * v + 1, tree[2 * v + 1].fi) + findSum(2 * v, k - tree[2 * v + 1].fi);
}
ll getSum(int k){
if(tree[1].fi <= k){
return tree[1].se;
}
return findSum(1, k);
}
void calc(int a, int b, int l, int p, vector<pll>& ret){
if(a > b){
return;
}
int mid = (a + b) / 2;
//policz f(mid)
int f = l;
for(int i = l; i <= p; i++){
upd(id[i], 1, A[i]);
if(i > mid){
continue;
}
ll val = getSum(mid - i);
if(val > ret[mid].se){
f = i;
ret[mid].fi = i;
ret[mid].se = val;
}
}
for(int i = l; i <= p; i++){
upd(id[i], -1, A[i]);
}
calc(a, mid - 1, l, f, ret);
for(int i = l; i <= f - 1; i++){
upd(id[i], 1, A[i]);
}
calc(mid + 1, b, f, p, ret);
for(int i = l; i <= f - 1; i++){
upd(id[i], -1, A[i]);
}
}
vector<pll> calcRes(vll x, int d){
if(sz(x) == 0){
vector<pll> res(d + 1, mp(0LL, 0LL));
return res;
}
id.resize(sz(x));
vector<pll> vec;
for(int i = 0; i < sz(x); i++){
vec.pb(mp(x[i], i));
}
sort(all(vec));
for(int i = 0; i < sz(vec); i++){
id[vec[i].se] = i;
}
A = x;
vector<pll> ret(d + 1, mp(0LL, 0LL));
calc(0, d, 0, sz(x) - 1, ret);
return ret;
}
//idziesz w lewo, zawracasz i idziesz w prawo
ll solve(vll left, vll right, int n, int d){
// cerr << "============\n";
// cerr << n << ' ' << d << '\n';
// debug(left);
// debug(right);
vector<pll> resL = calcRes(left, d);
vector<pll> resR = calcRes(right, d);
// debug(resL);
// debug(resR);
ll ans = 0LL;
for(int i = 0; i <= d; i++){
ans = max(ans, resL[i].se);
ans = max(ans, resL[i].se + resR[max(0LL, d - i - resL[i].fi - 1)].se);
}
return ans;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
vll a = {};
vll b = {};
for(int i = 0; i < start; i++){
a.pb(attraction[i]);
}
a.pb(attraction[start]);
for(int i = n - 1; i > start; i--){
b.pb(attraction[i]);
}
reverse(all(a));
reverse(all(b));
ll ans = solve(a, b, n, d);
reverse(all(a));
reverse(all(b));
a.pop_back();
b.pb(attraction[start]);
reverse(all(a));
reverse(all(b));
ans = max(ans, solve(b, a, n, d));
return ans;
}
// int main(){
// int n, start, d;
// int attraction[100000];
// cin >> n >> start >> d;
// for(int i = 0; i < n; i++){
// cin >> attraction[i];
// }
// cout << findMaxAttraction(n, start, d, attraction) << '\n';
// return 0;
// }
