#include"holiday.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
using ll = long long;
const int N = 1e5 + 123;
int n;
#define cout if(false)cout
pair<int,int>pp[N];
int cnt[N << 2];
ll sum[N << 2];
void upd(int pos, int type, int l = 0, int r = n, int v = 1) {
if (r - l == 1) {
cnt[v] += type, sum[v] += type * pp[l].first;
return;
}
int m = (l + r) >> 1;
if (pos < m) upd(pos, type, l, m, v << 1);
else upd(pos, type, m, r, v<<1|1);
cnt[v] = cnt[v << 1] + cnt[v<<1|1];
sum[v] = sum[v << 1] + sum[v<<1|1];
}
ll get(int &y, int l = 0, int r = n, int v = 1) {
if (!y || !cnt[v]) return 0;
if (cnt[v] <= y) {
y -= cnt[v];
return sum[v];
}
int m = (l + r) >> 1;
ll res = get(y, m, r, v<<1|1);
res += get(y, l, m, v << 1);
return res;
}
int pos[N];
ll ans;
int start, d;
void solve(int l, int r, int opl, int opr) {
if (l > r) return;
int m = (l + r) >> 1;
int opm = -1;
cout << "---\n";
for (int i = m ; i < opl ; ++ i) {
upd(pos[i], 1);
cout << "add " << i << " " << pp[pos[i]].first << endl;
}
int x = d - (start - m);
ll cur = 0;
cout << m << " " << x << " m\n";
opm = opl;
for (int i = opl ; i <= opr ; ++ i) {
upd(pos[i], 1);
cout << "add " << i << " " << pp[pos[i]].first << endl;
int y = x - (i - m);
if (y >= 0) {
cout << i << " " << m << " " << y;
ll temp = get(y);
cout << " " << temp << endl;
if (temp > cur) {
opm = i;
cur = temp;
}
}
}
for (int i = m ; i <= opr ; ++ i) {
upd(pos[i], -1);
}
cout << m << " " << cur << endl;
ans = max(ans, cur);
solve(l, m - 1, opl, opm);
solve(m + 1, r, opm, opr);
}
ll findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
n = n_, start = start_, d = d_;
for (int i = 0 ; i < n ; ++ i) {
pp[i] = {attraction[i], i};
}
sort(pp, pp + n);
for (int i = 0 ; i < n ; ++ i) {
cout << pp[i].first << " ";
}
cout << endl;
for (int i = 0 ; i < n ; ++ i) {
pos[pp[i].second] = i;
}
for (int _ = 0 ; _ < 2 ; ++ _) {
cout << "\n";
for (int i = 0 ; i < n ; ++ i) {
cout << attraction[i] << " ";
}
cout << endl;
solve(0, start, start, n - 1);
for (int i = 0 ; i < n ; ++ i) {
pp[i].second = n - pp[i].second - 1;
pos[pp[i].second] = i;
}
reverse(attraction, attraction + n);
start = n - start - 1;
}
return ans;
}
