/**
____ ____ ____ __________________ ____ ____ ____
||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 pair <int, int> pii;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , ll> pil;
typedef pair <ll , int> pli;
typedef long double ld;
std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;
double timePassed()
{
using namespace std::chrono;
currT = high_resolution_clock::now();
double time = duration_cast<duration<double>>(currT - startT).count();
return time * TIME_MULT;
}
pii tree[maxn * 4];
int ta[maxn];
int a[maxn];
int n;
void update(int node , int l , int r , int qp , int qval)
{
if(l > qp)
return;
if(r < qp)
return;
if(l == r)
{
tree[node] = {qval , qval * ta[l]};
return;
}
int 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(int node , int l , int r , int br)
{
if(l == r)
return ta[l] * br;
int 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);
}
int le , ri;
int sz;
int dist , start;
int dp[maxn];
void dnc(int l , int r , int optl , int optr)
{
if(l > r)
return;
int 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--;
}
int new_opt = -1;
for(int i = optl; i <= optr; i++)
{
if(i != optl)
{
ri++;
update(1 , 1 , sz , a[ri] , 1);
}
int br = max(dist - (start + i) + mid * 2 ,
dist + start + mid - i * 2);
br = min(br , i - mid + 1);
int 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);
}
long long int findMaxAttraction(int N , int START , int D , int attraction[])
{
n = N;
start = START;
dist = D;
for(int i = 0; i < n; i++)
a[i] = attraction[i];
le = start;
ri = start - 1;
vector <int> val;
for(int 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();
int save;
for(int 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] = -INF;
}
dnc(0 , start , start , n - 1);
return *max_element(dp , dp + n);
}
/**
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();
read();
solve();
return 0;
}
*/
