#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int dmax = 400001;
const int nmax = 200001;
struct node{
ll val;
ll x;
node(){
val = x = 0;
return;
}
}t[4 * nmax];
void upd(int v, int l, int r, int pos, ll val){
if(l > pos || r < pos)
return;
if(l == r){
t[v].val = val;
t[v].x = (val > 0);
if(val > 1e9)
t[v].x = val;
return;
}
int m = (l + r) / 2;
upd(2 * v, l, m, pos, val);
upd(2 * v + 1, m + 1, r, pos, val);
t[v].val = t[v * 2].val + t[v * 2 + 1].val;
t[v].x = t[v * 2].x + t[v * 2 + 1].x;
}
ll get(int v, int l, int r, int val){
if(l == r){
return 0;
}
int m = (l + r) /2;
if(t[v * 2].x <= val)
return t[v * 2].val + get(2 * v + 1, m + 1, r, val - t[v * 2].x);
return get(2 * v, l, m, val);
}
pll ans[dmax][4];
ll a[nmax];
int b[nmax];
//op=0 --->
//op=1 <---
int n;
void divide_and_conquer(int l, int r, int optl, int optr, int op, int st, int ind){
int m = (l + r) / 2;
if(l > r)
return;
pll mx = {0, optl};
if(op == 0){
for(int j = optl; j <= optr; j++){
upd(1, 1, n + 1, b[j], a[j]);
ll cur = get(1, 1, n + 1, m - j + st);
if(cur > mx.f)
mx.f = cur, mx.s = j;
}
ans[m][ind] = mx;
for(int j = optl; j <= optr; j++)
upd(1, 1, n + 1, b[j], 0);
divide_and_conquer(l, m - 1, optl, mx.s, op, st, ind);
for(int j = optl; j < mx.s; j++){
upd(1, 1, n + 1, b[j], a[j]);
}
divide_and_conquer(m + 1, r, mx.s, optr, op, st, ind);
for(int j = optl; j <= optr; j++)
upd(1, 1, n + 1, b[j], 0);
}
else {
mx.s = optr;
for(int j = optr; j >= optl; j--){
upd(1, 1, n + 1, b[j], a[j]);
ll cur = get(1, 1, n + 1, m - st + j);
if(cur > mx.f)
mx.f = cur, mx.s = j;
}
ans[m][ind] = mx;
for(int j = optl; j <= optr; j++)
upd(1, 1, n + 1, b[j], 0);
divide_and_conquer(l, m - 1, mx.s, optr, op, st, ind);
for(int j = optr; j > mx.s; j--){
upd(1, 1, n + 1, b[j], a[j]);
}
divide_and_conquer(m + 1, r, optl, mx.s, op, st, ind);
for(int j = optl; j <= optr; j++)
upd(1, 1, n + 1, b[j], 0);
}
return;
}
long long findMaxAttraction(int N, int start, int d, int attraction[]) {
n = N;
pii c[n + 1];
for(int i = 1; i <= N; i++)
a[i] = attraction[i - 1];
for(int i = 1; i <= n; i++){
c[i] = {a[i], i};
}
upd(1, 1, n + 1, n + 1, 1e9 + 1);
sort(c + 1, c + n + 1);
reverse(c + 1, c + n + 1);
for(int i = 1; i <= n; i++)
b[c[i].s] = i;
start++;
divide_and_conquer(0, d, start, n, 0, start, 0);
divide_and_conquer(0, d, 1, start, 1, start, 1);
// cout << ans[d][0].f << ' ' << ans[d][1].f << "\n";
if(start == 1){
return ans[d][0].f;
}
if(start == n)
return ans[d][1].f;
divide_and_conquer(0, d, start + 1, n, 0, start + 1, 2);
divide_and_conquer(0, d, 1, start - 1, 1, start - 1, 3);
ll x = max(ans[d][0].f, ans[d][1].f);
for(int i = 1; i < d; i++){
ll u = ans[i][0].f;
ll pos = ans[i][0].s;
ll rem = d - i - (pos - start);
rem--;
if(rem > 0)x = max(x, u + ans[rem][3].f);
u = ans[i][1].f;
pos = ans[i][1].s;
rem = d - i - (start - pos);
rem--;
if(rem)x = max(x, u + ans[rem][2].f);
}
return x;
}
