#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
const int INF = 2e9;
const ll INFLL = 4e18;
const int mod = 1e9+7;
const int N = 1e5+1;
const int logn = 20;
struct tree_node{
int cnt,lt,rt;
ll sum;
};
tree_node segtree[N*logn];
int segtree_node_cnt = 0;
int update(int node, int i, int j, int ind, int val){
int curr_node = ++segtree_node_cnt;
segtree[curr_node] = segtree[node];
segtree[curr_node].cnt++;
segtree[curr_node].sum += val;
if(i == j) return curr_node;
int mid = (i+j)>>1;
if(ind <= mid) segtree[curr_node].lt = update(segtree[node].lt,i,mid,ind,val);
else segtree[curr_node].rt = update(segtree[node].rt,mid+1,j,ind,val);
return curr_node;
}
void query(int nodelt, int nodert, int i, int j, int &count, ll &sum) {
if(count <= 0 || nodert == 0) return;
if(segtree[nodert].cnt - segtree[nodelt].cnt <= count){
count -= segtree[nodert].cnt - segtree[nodelt].cnt;
sum += segtree[nodert].sum - segtree[nodelt].sum;
return;
}
if(i==j){
ll temp = segtree[nodert].sum - segtree[nodelt].sum;
temp /= segtree[nodert].cnt - segtree[nodelt].cnt;
temp *= count;
count = 0;
sum += temp;
}
else{
int mid = (i+j)>>1;
query(segtree[nodelt].rt, segtree[nodert].rt, i, mid, count, sum);
query(segtree[nodelt].lt, segtree[nodert].lt, mid+1, j, count, sum);
}
}
int node_nums[N];
long long int find_range_ans(int l, int r, const int &d, const int &start, const bool &repeat_from_left){
if(start < l || start > r) return 0;
ll ans = 0;
int cnt = r-l;
if(repeat_from_left) cnt += start-l;
else cnt += r-start;
cnt = d-cnt;
query(node_nums[l-1], node_nums[r], 1, N, cnt, ans);
return ans;
}
void dnc(int lt_l, int lt_r, int rt_l, int rt_r, const bool repeat_from_left, const int &d, ll &ans, const int &start){
if(rt_l > rt_r) return;
int rt_mid = (rt_l + rt_r) / 2;
int lt_mid = lt_l;
ll curr_ans = 0;
for(int i = lt_l; i <= lt_r; i++){
ll curr = find_range_ans(i, rt_mid, d, start, repeat_from_left);
if(curr >= curr_ans){
curr_ans = curr;
lt_mid = i;
}
}
ans = max(ans,curr_ans);
dnc(lt_l, lt_mid, rt_l, rt_mid - 1, repeat_from_left, d, ans, start);
dnc(lt_mid, lt_r, rt_mid + 1, rt_r, repeat_from_left, d, ans, start);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]){
start++;
int temp[n];
for(int i = 0; i < n; i++) temp[i+1] = attraction[i];
sort(temp+1,temp+n+1);
for(int i = 0; i < n; i++){
int index = lower_bound(temp + 1, temp + n + 1, attraction[i]) - temp;
node_nums[i+1] = update(node_nums[i], 1, N, index, attraction[i]);
}
ll ans = 0;
if(start == 1){
for(int i = 1; i <= n; i++) ans = max(ans,find_range_ans(start,i,d,start,true));
return ans;
}
dnc(1, start, start, n, true, d, ans, start);
dnc(1, start, start, n, false, d, ans, start);
return ans;
}
void solve(){
int n,start,d;
cin >> n >> start >> d;
int attraction[n];
for(int i = 0; i < n; i++) cin >> attraction[i];
cout << findMaxAttraction(n,start,d,attraction) << "\n";
}
// int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int t = 1;
// // cin >> t;
// while(t--) {
// solve();
// }
// }
