#include "holiday.h"
#include <bits/stdc++.h>
#define lll long long
#define ldb long double
#define pii pair<int,int>
#define pll pair<lll,lll>
#define pil pair<int,lll>
#define pli pair<lll,int>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define maxn 100000
#define maxf 100
using namespace std;
int n;
int v[maxn+5], fv[maxf+5], wh[maxn+5];
pli aint[4*maxn+5];///fi=suma itv,se=nr de 0 pe itv
pii u[maxn+5];///fi=v[i],se=i
lll ans;
void umax (lll &a, lll b) { a = max(a,b); }
void update (int p, pii itv, int ind) {
if (wh[ind] < itv.fi || itv.se < wh[ind]) return;
if (itv.fi == itv.se) {
if (aint[p].fi == 0) aint[p] = {1LL*v[ind], 0};
else aint[p] = {0, 1};
return;
}
int mid = (itv.fi + itv.se) / 2;
update (p*2, {itv.fi, mid}, ind);
update (p*2+1, {mid+1, itv.se}, ind);
aint[p] = {aint[p*2].fi+aint[p*2+1].fi, aint[p*2].se+aint[p*2+1].se};
}
void preupdate (int ind) { update(1, {1,n}, ind); }
int dif0 (pii itv, pii con) { return itv.se-itv.fi+1 - con.se; }
lll q_query;///vreau suma celor mai mari k nr din aint
void query (int p, pii itv, int cat) { ///iau din itv cele mai mari cat nr
if (cat <= 0) return;
if (cat == dif0(itv, aint[p])) { q_query += aint[p].fi; return; }
if (itv.fi == itv.se) return;
int mid = (itv.fi + itv.se) / 2;
if (cat > dif0({itv.fi, mid}, aint[p*2])) {
query (p*2, {itv.fi, mid}, dif0({itv.fi, mid}, aint[p*2]));
query (p*2+1, {mid+1, itv.se}, cat - dif0({itv.fi, mid}, aint[p*2]));
} else query (p*2, {itv.fi, mid}, cat);
}
lll prequery (int cat) {
q_query = 0;
cat = min(cat, dif0({1,n}, aint[1]));
query (1, {1,n}, cat);
return q_query;
}
lll biggest (int rem) {
int nr; lll cur = 0;
for (nr = maxf; nr > 0 && rem > 0; nr--)
if (rem > fv[nr]) {
cur += 1LL * fv[nr] * nr;
rem -= fv[nr];
} else {
cur += 1LL * rem * nr;
rem = 0;
}
return cur;
}
int minpasi (int start, int a, int b) { return b-a+min(start-a, b-start); }
lll findMaxAttraction (int n_, int start_, int d_, int* v_) {
n = n_;
int start = start_, d = d_;
int i, j, z;
if (start == 0) {
for (i = 0; i < n; i++) v[i] = v_[i];
for (j = 0; j < n; j++) {
fv[v[j]]++;
umax(ans, biggest(d-j));
}
} else {
start++;///!!!!
for (i = 1; i <= n; i++) v[i] = v_[i-1];
for (i = 1; i <= n; i++) u[i] = {v[i], i};
sort(u+1, u+n+1, [](pii a, pii b) {return a.fi > b.fi;});
for (i = 1; i <= n; i++) wh[u[i].se] = i;
int a, b;
for (a = start; a >= 1; a--) {
for (b = start; b <= n; b++) {
preupdate(b);
umax (ans, prequery(d-minpasi(start, a, b)));
}
for (b = n; b >= start; b--) preupdate(b);
if (a > 1) preupdate(a-1);
}
}
return ans;
}
