#include "holiday.h"
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T> void print(deque <T> v);
template <class T> void print(queue <T> q);
template <class T> void print(priority_queue <T> q);
template <class T> void print(int n, T arr[]);
template <class T> void print(stack <T> st);
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(queue <T> q) {cerr << "[ "; while(!q.empty()) {print(q.front()); cerr << " "; q.pop();} cerr << "]";}
template <class T> void print(priority_queue <T> q) {cerr << "[ "; while(!q.empty()) {print(q.top()); cerr << " "; q.pop();} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(int n, T arr[]) {cerr << "[ "; for(int i = 0; i <= n; i++) {print(arr[i]); cerr << " ";} cerr << "]\n";}
template <class T> void print(stack <T> st) {cerr << "[ "; while(!st.empty()) {print(st.top()); st.pop(); cerr << ' ';} cerr << "]\n";}
#define pb push_back
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define noAnsw cout << -1 << '\n'
#define ll long long
#define ppb pop_back
#define OK cout << "OK" << endl;
#define ld long double
#define all(v) (v).begin(), (v).end()
#define MP make_pair
#define PII pair <int, int>
#define endl '\n'
#define ull unsigned long long
#define PLL pair <ll, ll>
#define PIL pair <int, ll>
#define PLI pair <ll, int>
#define rall(v) (v).rbegin(), (v).rend()
#define priora priority_queue
#define urishOK cout << "urishOK\n";
const int N = 1e5 + 5, LOG = 31, inf = 1e9 + 5;
int root[N], opt[N];
struct SegmentTree{
int timer;
struct node{
int cnt, lx, rx;
ll sum;
} tree[N * LOG];
void reset(){
for(int i = 0; i < N * LOG; i++) tree[i] = {0, 0, 0, 0};
timer = 1;
}
int upd(int i, int root){
return upd(i, root, 0, inf);
}
int upd(int i, int x, int lx, int rx){
tree[timer] = tree[x];
if(rx == lx + 1){
tree[timer].cnt++;
tree[timer].sum += i;
return timer++;
}
int mx = (lx + rx) / 2, lef = tree[x].lx, rig = tree[x].rx;
if(i < mx){
lef = upd(i, tree[x].lx, lx, mx);
}
else{
rig = upd(i, tree[x].rx, mx, rx);
}
tree[timer] = {tree[lef].cnt + tree[rig].cnt, lef, rig, tree[lef].sum + tree[rig].sum};
return timer++;
}
ll qry(int l, int r, int k){
return qry(k, root[l - 1], root[r], 0, inf);
}
ll qry(int k, int L, int R, int lx, int rx){
if(k <= 0) return 0;
if(tree[R].cnt - tree[L].cnt <= k) return tree[R].sum - tree[L].sum;
int mx = (lx + rx) / 2;
return qry(k, tree[L].rx, tree[R].rx, mx, rx) + qry(k - (tree[tree[R].rx].cnt - tree[tree[L].rx].cnt), tree[L].lx, tree[R].lx, lx, mx);
}
} st;
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
st.reset();
ll answ = 0;
for(int i = 1; i <= n; i++){
root[i] = st.upd(attraction[i - 1], root[i - 1]);
}
for(int R = start + 1; R <= n; R++){
for(int L = start + 1; L >= 1; L--){
answ = max(answ, st.qry(L, R, d - 2 * (start + 1 - L) - (R - start - 1)));
}
}
st.reset();
for(int i = 0; i < n / 2; i++) swap(attraction[i], attraction[n - 1 - i]);
for(int i = 1; i <= n; i++){
root[i] = st.upd(attraction[i - 1], root[i - 1]);
}
start = n - 1 - start;
for(int R = start + 1; R <= n; R++){
for(int L = start + 1; L >= 1; L--){
answ = max(answ, st.qry(L, R, d - 2 * (start + 1 - L) - (R - start - 1)));
}
}
return answ;
}
