#include"holiday.h"
#include<algorithm>
#define DIM 100005
#define DIM2 250005
#define f first
#define s second
using namespace std;
int v[DIM], nr;
long long dp[DIM2], e[2][DIM2], e2[2][DIM2];
pair<int, int> w[DIM];
pair<long long, int> aint[4 * DIM];
void copiere(long long a[], long long b[], int d){
for(int i = 1; i <= d; i++){
a[i] = b[i];
}
}
void build(int n){
for(int i = 1; i <= 4 * n; i++){
aint[i] = make_pair(0, 0);
}
}
void update(int nod, int st, int dr, int p, int val){
if(st == dr){
aint[nod].s = val;
aint[nod].f = val * w[st].f;
}
else{
int mid = (st + dr) / 2;
if(p <= mid){
update(2 * nod, st, mid, p, val);
}
else{
update(2 * nod + 1, mid + 1, dr, p, val);
}
aint[nod].f = aint[2 * nod].f + aint[2 * nod + 1].f;
aint[nod].s = aint[2 * nod].s + aint[2 * nod + 1].s;
}
}
long long query(int nod, int st, int dr, int nr){
if(aint[nod].s <= nr){
return aint[nod].f;
}
else{
int mid = (st + dr) / 2;
if(aint[2 * nod + 1].s >= nr){
return query(2 * nod + 1, mid + 1, dr, nr);
}
else{
return aint[2 * nod + 1].f + query(2 * nod, st, mid, nr - aint[2 * nod + 1].s);
}
}
}
void solve(int p, int u, int st, int dr, int ad){
if(p > u){
return;
}
int i, mid, x = 0;
long long sol = 0, val;
mid = (p + u) / 2;
for(i = st; i <= dr; i++){
update(1, 1, nr, v[i], 1);
if(i * ad <= mid){
val = query(1, 1, nr, mid - i * ad);
if(val > sol){
sol = val;
x = i;
}
}
}
dp[mid] = sol;
for(i = st; i <= dr; i++){
update(1, 1, nr, v[i], 0);
}
solve(p, mid - 1, st, x, ad);
for(i = st; i < x; i++){
update(1, 1, nr, v[i], 1);
}
solve(mid + 1, u, x, dr, ad);
for(i = st; i < x; i++){
update(1, 1, nr, v[i], 0);
}
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
int i, j;
long long sol = 0;
if(start != n - 1){
nr = 0;
for(i = start + 1; i < n; i++){
w[++nr] = make_pair(attraction[i], i - start);
}
sort(w + 1, w + nr + 1);
build(nr);
for(i = 1; i <= nr; i++){
v[ w[i].s ] = i;
}
solve(1, d, 1, nr, 1);
copiere(e[0], dp, d);
solve(1, d, 1, nr, 2);
copiere(e[1], dp, d);
}
if(start != 0){
nr = 0;
for(i = start - 1; i >= 0; i--){
w[++nr] = make_pair(attraction[i], start - i);
}
sort(w + 1, w + nr + 1);
build(nr);
for(i = 1; i <= nr; i++){
v[ w[i].s ] = i;
}
solve(1, d, 1, nr, 1);
copiere(e2[0], dp, d);
solve(1, d, 1, nr, 2);
copiere(e2[1], dp, d);
}
for(i = 1; i <= d; i++){
e[0][i] = max(e[0][i], e[0][i - 1]);
e[1][i] = max(e[1][i], e[1][i - 1]);
e2[0][i] = max(e2[0][i], e2[0][i - 1]);
e2[1][i] = max(e2[1][i], e2[1][i - 1]);
}
for(i = d; i >= 1; i--){
e[0][i] = max(e[0][i], e[0][i - 1] + attraction[start]);
e[1][i] = max(e[1][i], e[1][i - 1] + attraction[start]);
}
for(i = 0; i <= d; i++){
sol = max(sol, e[0][i] + e2[1][d - i]);
sol = max(sol, e[1][i] + e2[0][d - i]);
}
return sol;
}
