#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
#define ll long long
#define pill pair<int,ll>
#define pi pair<int,int>
#define f first
#define s second
/***********************/
struct SegTree{
vector<pill> st;
vector<pi> minmax;
int sz;
SegTree(int n){
sz = n;
st.assign(n*4, {0,0ll});
minmax.assign(n*4, {0,0});
}
void updactive(int n, int l, int r, int ind, int val){
if(l == r){
st[n].f = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updactive(2*n+1, l, mid, ind, val);
else
updactive(2*n + 2, mid + 1, r, ind, val);
st[n].f = st[2*n+1].f + st[2*n+2].f;
}
void updval(int n, int l, int r, int ind, int val){
if(l == r){
st[n].s = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updval(2*n+1, l, mid, ind, val);
else
updval(2*n + 2, mid + 1, r, ind, val);
st[n].s = st[2*n+1].s + st[2*n+2].s;
}
void updmin(int n, int l, int r, int ind, int val){
if(l == r){
minmax[n].f = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updmin(2*n + 1, l, mid, ind , val);
else
updmin(2*n+2, mid + 1, r, ind , val);
minmax[n].f = min(minmax[2* n +1].f, minmax[2*n + 2].f);
}
void updmax(int n, int l, int r, int ind, int val){
if(l == r){
minmax[n].s = val;
return;
}
int mid = (l + r)/2;
if(mid >= ind)
updmax(2*n + 1, l, mid, ind , val);
else
updmax(2*n+2, mid + 1, r, ind , val);
minmax[n].s = max(minmax[2* n +1].s, minmax[2*n + 2].s);
}
void activate(int ind,int city, int val){
updactive(0,0,sz, ind, 1);
updval(0,0,sz, ind, val);
updmin(0,0,sz,ind, city);
updmax(0,0,sz,ind,city);
}
int getfirst(int n, int l, int r, int val){
if(l == r) return l;
int mid = (l + r)/2;
if(st[2*n+1].f >= val )
return getfirst(2*n+1, l, mid, val);
return getfirst(2*n+ 2, mid + 1, r, val - st[2*n+1].f);
}
int getfirst(int val){
int target = st[0].f - val +1;
if(target <=0)
return 0;
return getfirst(0, 0, sz, target);
}
ll qrysum(int n, int l, int r, int s, int e){
if(s<= l and e >= r) return st[n].s;
ll ans = 0;
int mid = (l + r)/2;
if( mid >= s)
ans += qrysum(2*n+1, l, mid, s, e);
if(mid < e)
ans+=qrysum(2*n+2, mid + 1, r, s,e);
return ans;
}
int getmin(int n, int l, int r, int s, int e){
if(s<= l and e >= r) return minmax[n].f;
int ans = 1e9;
int mid = (l + r)/2;
if( mid >= s)
ans = min(getmin(2*n+1, l, mid, s, e), ans);
if(mid < e)
ans = min(getmin(2*n+2, mid + 1, r, s,e), ans);
return ans;
}
int getmax(int n, int l, int r, int s, int e){
if(s<= l and e >= r) return minmax[n].s;
int ans = -1;
int mid = (l + r)/2;
if( mid >= s)
ans = max(getmax(2*n+1, l, mid, s, e), ans);
if(mid < e)
ans = max(getmax(2*n+2, mid + 1, r, s,e),ans);
return ans;
}
pair<ll, pi> getlargest(int rng){
int lower = getfirst(rng);
//cout << lower<<endl;
return {qrysum(0, 0,sz, lower, sz ), {getmin(0, 0,sz, lower,sz), getmax(0,0,sz,lower,sz)}};
}
};
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
vector<pi> cities(n);
for(int i =0; i<n; i++){
cities[i] = {attraction[i], i};
}
sort(cities.begin(), cities.end());
vector<int> inds(n);
for(int i= 0; i<n;i++)
inds[cities[i].s] = i;
vector<ll> dpright(d+1, 0);
vector<int> minright(d + 1, 1e9);
for(int days =1; days<=d; days++){
SegTree stright(n);
for(int right = start; right <n; right++){
stright.activate(inds[right],right, attraction[right]);
int dist = right - start;
if(days - dist <= 0)
break;
pair<ll, pi> res = stright.getlargest(days - dist);
if(res.f > dpright[days]){
dpright[days] = res.f;
minright[days] = res.s.s;
}
else if(res.f == dpright[days]){
minright[days] = min(minright[days], res.s.s);
}
}
}
vector<ll> dpleft(d+1, 0);
vector<int> maxleft(d + 1, -1);
for(int days =1; days<=d; days++){
SegTree stleft(n);
for(int left = start -1; left >=0; left--){
stleft.activate(inds[left],left, attraction[left]);
int dist = start - left;
if(days - dist <= 0)
break;
pair<ll, pi> res = stleft.getlargest(days - dist);
if(res.f > dpleft[days]){
dpleft[days] = res.f;
maxleft[days] = res.s.f;
}
else if(res.f == dpright[days]){
maxleft[days] = max(maxleft[days], res.s.f);
}
}
}
ll ans = 0;
for(int daysright = 0; daysright <= d; daysright++){
int distright = daysright == 0 ? 0: minright[daysright] - start;
int daysleft = max(0,max(d - daysright - distright , (d - daysright)/2));
//cout<< daysleft<<", "<<daysright<<", "<<distright<<": "<<dpleft[daysleft]<<", "<<dpright[daysright]<<endl;
ans = max(ans,dpleft[daysleft] + dpright[daysright] );
}
return ans;
}
/***********************/
