#include "holiday.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n , a[maxn];
ll s[maxn * 4];
int cnt[maxn * 4];
ll res = 0;
int order[maxn] , d , id[maxn];
int st = 0;
void flip(int x , int l , int r , int pos){
if(l == r){
// cout << pos << " " << a[id[l]] << endl;
if(cnt[x] == 0)cnt[x] = 1 , s[x] = a[order[l]];
else cnt[x] = 0 , s[x] = 0;
return;
}
int mid = l + r >> 1;
if(pos <= mid)flip(x * 2 , l , mid , pos);
else flip(x * 2 + 1 , mid + 1 , r , pos);
s[x] = s[x * 2] + s[x * 2 + 1];
cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
}
ll get(int x , int l , int r , int k){
if(cnt[x] <= k)return s[x];
if(l == r || k <= 0)return 0;
ll sum = 0;
int mid = l + r >> 1;
sum += get(x * 2 + 1 , mid + 1 , r , min(k , cnt[x * 2 + 1]));
k -= min(k , cnt[x * 2 + 1]);
sum += get(x * 2 , l , mid , k);
return sum;
}
void flip(int pos){flip(1,1,n,pos);}
ll get(int k){return get(1,1,n,k);};
int L = 1 , R = 0;
void correct(int l , int r){
while(L < l)flip(id[L++]);
while(L > l)flip(id[--L]);
while(R < r)flip(id[++R]);
while(R > r)flip(id[R--]);
}
void solve(int l , int r , int optl , int optr){
if(l > r)return;
int mid = l + r >> 1;
pair<ll,int> best = mp(-1,-1);
for(int i = optl ; i <= mid && i <= optr ; ++i){
correct(i , mid);
best = max(best , mp(get(d - (mid - i) - (mid - st)) , i));
// cout << i << " " << mid << " " << cnt[1] << " " << d - (mid - i) - (mid - st) << " " << get(d - (mid - i) - (mid - st)) << endl;
}
res = max(res,best.first);
solve(l , mid - 1 , optl , best.second);
solve(mid + 1 , r , best.second,optr);
}
void Try(){
L = 1 , R = 0;
memset(cnt,0,sizeof cnt);
memset(s,0,sizeof s);
iota(order + 1 , order + n + 1 ,1);
sort(order + 1 , order + n + 1 ,[&](const int x , const int y){return a[x] < a[y];});
// for(int i = 1 ; i <= n ; ++i)cout << order[i] << " ";cout << endl;
for(int i = 1 ; i <= n ; ++i)id[order[i]] = i;
solve(st , n , 1 , n);
}
ll findMaxAttraction(int _n, int start, int _d, int attraction[]) {
n = _n;
st = start + 1;d = _d;
for(int i = 1 ; i <= n ; ++i)a[i] = attraction[i - 1];
Try();
for(int i = 1 ; i <= n ; ++i)a[i] = attraction[n - i];
st = n - start;
Try();
return res;
}
//static int N, start, D, A[100005];
//
//int main() {
// scanf("%d%d%d", &N, &start, &D);
// for ( int i = 0; i < N; i++ ) scanf("%d", &A[i]);
// printf("%lld\n", findMaxAttraction(N, start, D, A));
//}
