#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
//#define fuck
const int N = 1e5 + 10;
struct item{
long long va;
int sz, l, r;
}seg[20*N];
void newleaf( int now, long long va, int sz ) {
seg[now].va = va, seg[now].sz = sz, seg[now].l = -1, seg[now].r = -1;
return ;
}
void newpar( int now, int l, int r ) {
seg[now].va = seg[l].va + seg[r].va, seg[now].sz = seg[l].sz + seg[r].sz, seg[now].l = l, seg[now].r = r;
return;
}
int ver[N], cnt = 1;
unordered_map<long long, int> mp;
long long va[N], ans = -1LL;
int n, s, d;
vector<long long> coord;
int build( int l = 1, int r = n ) {
if( l == r ) {
int now = cnt;
cnt++;
newleaf( now, 0, 0 );
return now;
}
int mid = ( l + r ) >> 1, now = cnt;
cnt++;
newpar( now, build( l, mid ), build( mid + 1, r ) );
return now;
}
int update( int idx, long long va, int now, int l = 1, int r = n ) {
if( l == r ) {
int now = cnt;
cnt++;
newleaf( now, va, 1 );
return now;
}
int mid = ( l + r ) >> 1, noww = cnt;
cnt++;
if( idx <= mid ) newpar( noww, update( idx, va, seg[now].l, l, mid ), seg[now].r );
else newpar( noww, seg[now].l, update( idx, va, seg[now].r, mid + 1, r ) );
return noww;
}
long long query( int a, int b, int idx, int l = 1, int r = n ) {
if( idx <= 0 ) return 0LL;
if( l == r ) return seg[b].va - seg[a].va;
int mid = ( l + r ) >> 1;
int diff = seg[seg[b].r].sz - seg[seg[a].r].sz;
if( diff >= idx ) return query( seg[a].r, seg[b].r, idx, mid + 1, r );
else return seg[seg[b].r].va - seg[seg[a].r].va + query( seg[a].l, seg[b].l, idx - diff, l, mid );
}
int cal( int l, int r ) {
int ret = r - l;
int x = abs( s - l ), y = abs( s - r );
return ret + min( x, y );
}
int get( long long x ) {
mp[x]++;
return lower_bound( coord.begin(), coord.end(), x ) - coord.begin() + mp[x];
}
// void solve( int l, int r, int lb, int rb ) {
// //printf("%d %d %d %d\n",l,r,lb,rb);
// if( l > r ) return ;
// int mid = ( l + r ) >> 1;
// long long nowans = -1LL, ind = lb;
// for( int i = max( lb, mid ) ; i <= min( mid + d -1, rb ) ; i++ ) {
// int cos = cal( mid, i );
// if( d - cos - 2 < 0 ) continue;
// long long temp = query( ver[mid], ver[i-1], d - cos - 2 );
// long long temp2 = va[mid] + ( ( i == mid ) ? 0 : va[i] );
// //printf("%lld %lld\n",temp,temp2);
// temp += temp2;
// if( temp > nowans ) ind = i, nowans = temp;
// }
// ans = max( ans, nowans );
// solve( l, mid - 1, lb, ind );
// solve( mid + 1, r, ind, rb );
// }
void solve(int l, int r, int optmin, int optmax)
{
if( l > r ) return;
int mid = (l + r)/2;
int optInd = optmin;
long long optAns = -1;
for(int g = optmin ; g <= optmax ; g++)
{
int walkDays = (s - mid) + (g - mid);
if(walkDays < 0) continue;
long long curAns = query(ver[mid] , ver[g] , d - walkDays);
if(curAns > optAns)
{
optInd = g;
optAns = curAns;
}
}
ans = max(ans , optAns);
solve(l , mid - 1 , optmin , optInd);
solve(mid + 1 , r , optInd , optmax);
}
long long findMaxAttraction( int N, int ST, int D, int ttt[] ) {
s = ST + 1, d = D, n = N;
for( int i = 0 ; i < n ; i++ ) {
va[i+1] = ( long long )ttt[i];
coord.emplace_back( ttt[i] );
}
sort( coord.begin(), coord.end() );
ver[0] = cnt;
build();
for( int i = 1 ; i <= n ; i++ ) {
ver[i] = cnt;
update( get( va[i] ), va[i], ver[i] );
}
//for( int i = 0 ; i <= n ; i++ ) printf("%d ",ver[i]);
//printf("\n");
// for( int i = max( 1, s - d + 1 ) ; i <= min( n, s + d - 1 ) ; i++ ) ans = max( ans, va[i]);
// solve( max( 1, s - d + 1 ), min( n, s + d - 1 ), 1, n );
s = n - s + 1;
solve( 1, s, s, n );
return ans;
}
#ifdef fuck
int main()
{
int n, va[100], st, d;
scanf("%d %d %d",&n,&st,&d);
for( int i = 0 ; i < n ; i++ ) scanf("%d",&va[i]);
cout << findMaxAttraction( n, st, d, va );
}
#endif
