#include "holiday.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y)-x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF (1LL<<60)
using namespace std;
typedef pair<int, int> P;
int V=0;
#define MAX_N (1<<17)
struct SegTree {
const int num;
const long long sum;
SegTree *left = NULL, *right = NULL;
SegTree(int n, long long s) : num(n), sum(s) { V++; }
long long rsum(int n, int l=0, int r=MAX_N) {
if (n == 0) return 0;
if (r-l==1) return sum;
long long s = 0;
if (right==NULL || n >= right->num) {
if (right) {
n -= right->num;
s += right->sum;
}
if (left) s += left->rsum(n, l, (l+r)/2);
}
else {
if (right) s += right->rsum(n, (l+r)/2);
}
return s;
}
SegTree *update(int p, int val, int l=0, int r=MAX_N) {
if (r-l == 1) {
SegTree *ret = new SegTree(1, val);
return ret;
}
int mid = (l+r)/2;
SegTree *a = left, *b = right;
if (p < mid) {
if (!left) left = new SegTree(0, 0);
a = left->update(p, val, l, mid);
}
else {
if (!right) right = new SegTree(0, 0);
b = right->update(p, val, mid, r);
}
SegTree *ret = new SegTree(num+1, sum+val);
ret->left = a;
ret->right = b;
return ret;
}
};
int D, W;
SegTree *seg[100001];
inline long long f(int d, int e) {
if (d <= e*W) return 0;
return seg[e]->rsum(d-e*W);
}
int best(int x, int bottom, int top) {
pair<long long, int> mp = make_pair(-1, -1);
for (int i=bottom; i<=top; i++) mp = max(mp, make_pair(f(x, i), -i));
return -mp._2;
}
void solve(int l, int r, int bottom, int top, vector<long long> &ret) {
if (l > r) return;
if (l == r) {
ret[l] = best(l, bottom, top);
return;
}
int mid = (l+r)/2;
int q = ret[mid] = best(mid, bottom, top);
solve(l, mid-1, bottom, q, ret);
solve(mid+1, r, q, top, ret);
}
vector<vector<long long> > solve(vector<int> &A) {
vector<P> ps;
rep(i, A.size()) ps.pb(P(A[i], i));
sort(all(ps));
seg[0] = new SegTree(0, 0);
rep(i, A.size()) seg[i+1] = seg[i]->update(index(ps, P(A[i], i)), A[i]);
vector<vector<long long> > ret(2, vector<long long>(D+1, 0));
for (W=1; W<=2; W++) {
solve(0, D, 0, A.size(), ret[W-1]);
rep(i, D+1) ret[W-1][i] = f(i, ret[W-1][i]);
}
for (int i=A.size(); i>=0; i--) delete seg[i];
return ret;
}
long long findMaxAttraction(int N, int S, int DD, int A[]) {
assert(N<=3000);
D = DD;
vector<int> left, right;
rep(i, S) left.pb(A[i]);
for (int i=S+1; i<N; i++) right.pb(A[i]);
reverse(all(left));
vector<vector<long long> > dpL = solve(left);
vector<vector<long long> > dpR = solve(right);
//cout<<"V="<<V<<"\n";
long long m = 0;
rep(w, 2) {
rep(i, D+1) m = max(m, dpL[w][i]+dpR[w^1][D-i]);
rep(i, D) m = max(m, dpL[w][i]+dpR[w^1][D-i-1]+A[S]);
}
return m;
}
