/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include "holiday.h"
#define maxn 100005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
using namespace std;
typedef long long ll;
typedef pair <int , int> pii;
pii tree[maxn * 4];
ll ta[maxn];
ll a[maxn];
ll n;
void update(ll node , ll l , ll r , ll qp , ll qval)
{
if(l > qp)
return;
if(r < qp)
return;
if(l == r)
{
tree[node] = {qval , qval * ta[l]};
return;
}
ll mid = (l + r) / 2;
update(node * 2 , l , mid , qp , qval);
update(node * 2 + 1 , mid + 1 , r , qp , qval);
tree[node] = {tree[node * 2].X + tree[node * 2 + 1].X , tree[node * 2].Y + tree[node * 2 + 1].Y};
}
ll query(ll node , ll l , ll r , ll br)
{
if(l == r)
return ta[l] * br;
ll mid = (l + r) / 2;
if(br - tree[node * 2 + 1].X > 0)
return query(node * 2 , l , mid , br - tree[node * 2 + 1].X)
+ tree[node * 2 + 1].Y;
else
return query(node * 2 + 1 , mid + 1 , r , br);
}
ll le , ri;
ll sz;
ll dist , start;
ll dp[maxn];
void dnc(ll l , ll r , ll optl , ll optr)
{
if(l > r)
return;
ll mid = (l + r) / 2;
while(le < mid)
{
update(1 , 1 , sz , a[le] , -1);
le++;
}
while(le > mid)
{
le--;
update(1 , 1 , sz , a[le] , 1);
}
while(ri < optl)
{
ri++;
update(1 , 1 , sz , a[ri] , 1);
}
while(ri > optl)
{
update(1 , 1 , sz , a[ri] , -1);
ri--;
}
ll new_opt = -1;
for(ll i = optl; i <= optr; i++)
{
if(i != optl)
{
ri++;
update(1 , 1 , sz , a[ri] , 1);
}
ll br = max(dist - (start + i) + mid * 2 ,
dist + start + mid - i * 2);
br = min(br , i - mid + 1);
ll q = query(1 , 1 , sz , br);
if(q > dp[i])
{
dp[i] = q;
new_opt = i;
}
}
dnc(l , mid - 1 , optl , new_opt);
dnc(mid + 1 , r , new_opt , optr);
}
ll findMaxAttraction(int N , int START , int D , int attraction[])
{
n = N;
start = START;
dist = D;
for(ll i = 0; i < n; i++)
a[i] = attraction[i];
le = start;
ri = start - 1;
vector <ll> val;
for(ll i = 0; i < n; i++)
val.pb(a[i]);
sort(val.begin() , val.end());
val.erase(unique(val.begin() , val.end()) , val.end());
sz = val.size();
ll save;
for(ll i = 0; i < n; i++)
{
save = a[i];
a[i] = upper_bound(val.begin() , val.end() , a[i]) - val.begin();
ta[a[i]] = save;
dp[i] = -LINF;
}
dnc(0 , start , start , n - 1);
ll ans = 0;
for(ll i = 0; i < n; i++)
ans = max(ans , dp[i]);
return ans;
}
/**int test[maxn];
int main()
{
#ifdef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
///startT = std::chrono::high_resolution_clock::now();
int nn , startt , dd;
cin >> nn >> startt >> dd;
for(int i = 0; i < nn; i++)
cin >> test[i];
cout << findMaxAttraction(nn , startt , dd , test) << endl;
return 0;
}*/
