#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define all(x) (x).begin() , (x).end()
#define X first
#define Y second
const int MAXN = (1 << 20) + 10;
const int LOG = 20;
const ll INF = 1e18;
ll n , d , start , ql , qr , ans , A[MAXN] , pos[MAXN] , fen[2][MAXN];
void add(int ind , int x , int val){
for(x++; x < MAXN ; x += x & -x) fen[ind][x] += val;
}
ll get(int x){
ll cur = 0 , res = 0;
for(int i = LOG - 1 ; i >= 0 ; i--){
int nxt = (cur + (1 << i));
if(fen[0][nxt] <= x){
x -= fen[0][nxt];
res += fen[1][nxt];
cur = nxt;
}
}
return res;
}
void ins(int x , int f){
add(0 , pos[x] , 1 * f);
add(1 , pos[x] , A[x] * f);
}
ll calc(int l , int r){
while(l < ql) ins(--ql , 1);
while(qr < r) ins(++qr , 1);
while(ql < l) ins(ql++ , -1);
while(r < qr) ins(qr-- , -1);
return get(d - (r - l) - (r - start));
}
void solve(int l , int r , int optl , int optr){
if(r < l) return;
int mid = l + r >> 1;
ll mx = -1 , opt = -1;
for(int i = optl ; i <= mid && i <= optr ; i++){
ll cost = calc(i , mid);
assert(fen[0][1 << LOG] == mid - i + 1);
if(mx < cost){
mx = cost;
opt = i;
}
}
ans = max(ans , mx);
solve(l , mid - 1 , optl , opt);
solve(mid + 1 , r , opt , optr);
}
long long int findMaxAttraction(int N, int START, int D, int attract[]) {
n = N; start = START; d = D;
vector<pii> vec;
for(int i = 0 ; i < n ; i++){
A[i] = attract[i];
vec.push_back({A[i] , i});
}
sort(all(vec) , greater<pii>());
for(int i = 0 ; i < n ; i++) pos[vec[i].Y] = i;
ql = 0 , qr = -1; solve(start , n - 1 , 0 , start);
reverse(A , A + n);
reverse(pos , pos + n);
fill(fen[0] , fen[0] + MAXN , 0);
fill(fen[1] , fen[1] + MAXN , 0); start = n - start - 1;
ql = 0 , qr = -1; solve(start , n - 1 , 0 , start);
return ans;
}
