#include "holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int ile[4*LIM], N;
pair<ll,ll>T[LIM], P[LIM];
ll sum[4*LIM], ans[LIM];
void upd1(int v, int x) {
v+=N;
while(v) {
ile[v]+=x;
v/=2;
}
}
int znajdz(int k) {
int v=1;
while(v<N) {
v*=2;
if(ile[v]<k) {
k-=ile[v];
++v;
}
}
return v-N;
}
void upd2(int v, ll x) {
v+=N;
while(v) {
sum[v]+=x;
v/=2;
}
}
ll cnt(int l, int r) {
l+=N; r+=N;
ll ans=sum[l];
if(l!=r) ans+=sum[r];
while(l/2!=r/2) {
if(l%2==0) ans+=sum[l+1];
if(r%2==1) ans+=sum[r-1];
l/=2; r/=2;
}
return ans;
}
void dc(int l, int r, int a, int b) {
if(b<a) return;
int mid=(a+b)/2;
ll ma=0, gdzie=l;
for(int i=l; i<=r; ++i) {
upd1(T[i].nd, 1);
upd2(T[i].nd, T[i].st);
if(mid==i && ma==0) {
ma=0;
gdzie=i;
}
if(0<mid-i && mid-i<=i+1) {
ll p=cnt(0, znajdz(mid-i));
if(p>ma) {
ma=p;
gdzie=i;
}
}
}
for(int i=r; i>=gdzie; --i) {
upd1(T[i].nd, -1);
upd2(T[i].nd, -T[i].st);
}
dc(gdzie, r, mid+1, b);
for(int i=gdzie-1; i>=l; --i) {
upd1(T[i].nd, -1);
upd2(T[i].nd, -T[i].st);
}
dc(l, gdzie, a, mid-1);
ans[mid]=ma;
}
vector<ll>licz(vector<ll>V) {
int n=V.size();
N=1;
while(N<2*n) N*=2;
rep(i, 2*N) ile[i]=ans[i]=sum[i]=0;
rep(i, n) P[i]={V[i], i};
sort(P, P+n);
reverse(P, P+n);
rep(i, n) T[P[i].nd]={P[i].st, i};
dc(0, n-1, 0, 2*n-1);
vector<ll>W;
rep(i, 2*n) W.pb(ans[i]);
return W;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<ll>V;
rep(i, n) V.pb(attraction[i]);
vector<ll>A1=licz(V);
return A1[min(int(A1.size()-1), d)];
}
