#include"holiday.h"
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)(x).size()
#define pb push_back
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5, MX = 3e6;
int cnt[MX], a[N], idx, lef[MX], rig[MX];
ll sum[MX];
vi m;
int szm;
int get(int x) { return lb(all(m), x) - m.begin(); }
// what to reset in each new node: cnt, sum, lef, rig
int build(int l = 0, int r = szm - 1) {
int cur = idx++;
cnt[cur] = sum[cur] = 0;
if(l == r) { lef[cur] = rig[cur] = 0; return cur; }
int mid = l + r >> 1;
lef[cur] = build(l, mid);
rig[cur] = build(mid + 1, r);
return cur;
}
int update(int i, int pos, int l = 0, int r = szm - 1) {
int cur = idx++;
lef[cur] = rig[cur] = 0;
cnt[cur] = cnt[pos] + 1; sum[cur] = sum[pos] + m[i];
// if(l == 0 && r == szm - 1) { cout << "_______" << i << ' ' << m[i] << endl; }
// if(l == 0 && r == szm - 1) { cout << "_______" << sum[pos] << ' ' << m[i] << endl; }
if(l == r) { return cur; }
int mid = l + r >> 1;
if(i <= mid) lef[cur] = update(i, lef[pos], l, mid), rig[cur] = rig[pos];
else lef[cur] = lef[pos], rig[cur] = update(i, rig[pos], mid + 1, r);
return cur;
}
vi roots;
ll get_kth(int l, int r, int k) {
ll ret = 0;
int ql = 0, qr = szm - 1;
int idl = roots[l - 1], idr = roots[r];
while(ql <= qr) {
assert(k >= 0);
if(k == 0) { return ret; }
if(ql == qr) { return ret + k * m[ql]; }
// cout << "-> " << ret << ' ' << k << endl;
// cout << ql << ' ' << qr << " : " << cnt[rig[idr]] - cnt[rig[idl]] << ' ' << sum[rig[idr]] - sum[rig[idl]] << endl;
// cout << endl;
int mid = ql + qr >> 1;
if(k >= cnt[rig[idr]] - cnt[rig[idl]]) {
qr = mid;
k -= cnt[rig[idr]] - cnt[rig[idl]];
ret += sum[rig[idr]] - sum[rig[idl]];
idl = lef[idl]; idr = lef[idr];
} else {
ql = mid + 1;
idl = rig[idl]; idr = rig[idr];
}
}
return ret;
}
int day, s;
ll dnc(int optl, int optr, int l, int r) {
if(l > r) return 0;
int mid = l + r >> 1;
if(2 * mid - optr - s > day) return dnc(optl, optr, l, mid - 1);
int opt = -1;
ll mx = -1;
for(int i = max(optl, mid - (day - (mid - s)) ); i <= optr; i++) {
int rem = day - (2 * mid - s - i);
ll gk = get_kth(i, mid, rem);
if(gk > mx) opt = i, mx = gk;
}
// cout << "_____" << optl << ' ' << optr << " : " << l << ' ' << r << endl;
// cout << mid << " : " << opt << ' ' << mx << endl << endl;
assert(opt != -1 && mx >= 0);
return max({mx, dnc(optl, opt, l, mid - 1), dnc(opt, optr, mid + 1, r)});
}
ll solve(int n, int st, int d) {
// for(int i = 1; i <= n; i++) cout << a[i] << ' '; cout << endl;
roots.clear(); idx = 1;
roots.pb(build());
for(int i = 1; i <= n; i++)
roots.pb(update(get(a[i]), roots.back()));//, cout << "_" << sum[roots.back()] << endl;
// cout << "____________" << szm << endl;
// for(int i = 0; i < szm; i++) cout << m[i] << ' '; cout << endl;
// cout << get_kth(1, 4, 3) << endl;
// cout << "____________" << endl;
s = st + 1; day = d;
// return 0; //
return dnc(1, s, s, n);
}
long long int findMaxAttraction(int n, int st, int d, int attraction[]) {
// cout << "-> ";
// for(int i = 0; i < n; i++) cout << attraction[i] << ' '; cout << endl;
// cout << "___" << endl;
for(int i = 1; i <= n; i++) a[i] = attraction[i - 1], m.pb(a[i]);
sort(all(m));
m.erase(unique(all(m)), m.end());
szm = sz(m);
ll ans = solve(n, st, d);
for(int i = 1; i < n - i + 1; i++) swap(a[i], a[n - i + 1]);
// return ans; //
return max(ans, solve(n, n - 1 - st, d));
}
