#include"holiday.h"

#include<cstring>

#include<algorithm>

typedef long long i64;

const int N=;

i64 ans=;

int v[N],*vs[N],S,D;

struct node{

    node*c[];

    int sz;

    i64 s;

}ns[N*],*np=ns,*rt[N];

i64 kmx(int L,int R,int x){

    node*w1=rt[L],*w2=rt[R+];

    i64 sum=;

    for(int i=;i>=;--i){

        int s=w1->c[]->sz-w2->c[]->sz;

        if(s<=x){

            x-=s;

            sum+=w1->c[]->s-w2->c[]->s;

            w1=w1->c[];

            w2=w2->c[];

        }else{

            w1=w1->c[];

            w2=w2->c[];

        }

    }

    return sum;

}

node*ins(node*w,int x,int v){

    node*u=++np,*u0=u;

    for(int i=;i>=;--i){

        int d=x>>i&;

        u->c[d^]=w->c[d^];

        u=u->c[d]=++np;w=w->c[d];

        u->sz=w->sz+;

        u->s=w->s+v;

    }

    return u0;

}

void calc1(int L,int R,int l,int r){

    if(L>R)return;

    int M=L+R>>,m=l,res=D-(S-M)*-(l-S);

    i64 mv=-;

    for(int i=l;i<=r&&res>=;++i,--res){

        i64 v=kmx(M,i,res);

        if(v>mv)mv=v,m=i;

    }

    if(ans<mv)ans=mv;

    calc1(L,M-,l,m);

    calc1(M+,R,m,r);

}

void calc2(int L,int R,int l,int r){

    if(L>R)return;

    int M=L+R>>,m=r,res=D-(M-S)*-(S-r);

    i64 mv=-;

    for(int i=r;i>=l&&res>=;--i,--res){

        i64 v=kmx(i,M,res);

        if(v>mv)mv=v,m=i;

    }

    if(ans<mv)ans=mv;

    calc2(L,M-,l,m);

    calc2(M+,R,m,r);

}

bool cmp(int*a,int*b){

    return *a>*b;

}

i64 findMaxAttraction(int n,int start,int d,int attr[]){

    rt[n]=ns->c[]=ns->c[]=ns;

    memcpy(v,attr,sizeof(int)*n);

    for(int i=;i<n;++i)vs[i]=v+i;

    std::sort(vs,vs+n,cmp);

    for(int i=;i<n;++i)*vs[i]=i;

    for(int i=n-;i>=;--i)rt[i]=ins(rt[i+],v[i],attr[i]);

    D=d;S=start;

    calc1(std::max(,S-d/),S,S,n-);

    calc2(S,std::min(n-,S+d/),,S);

    return ans;

}

#include"grader.cpp"