#include"holiday.h"
#include <bits/stdc++.h>
#define mid ((st+dr)>>1)
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int Nmax = 1e5 + 5;
const int lim = 1e9;
ll ans[Nmax];
int best[Nmax];
int T, K;
struct Node
{
Node *left, *right;
ll sum; int sz;
Node()
{
left = right = NULL;
sum = 0;
sz = 0;
}
Node(Node *_left, Node *_right, ll _sum, int _sz)
{
left = _left; right = _right;
sum = _sum; sz = _sz;
}
Node(Node *_left, Node *_right)
{
left = _left; right = _right;
sum = (left ? left->sum : 0) + (right ? right->sum : 0);
sz = (left ? left->sz : 0) + (right ? right->sz : 0);
}
Node* update(int st, int dr, int pos)
{
if(st == dr)
return new Node(left, right, sum + pos, sz + 1);
if(pos <= mid)
{
if(!left) left = new Node();
return new Node( left->update(st, mid, pos), right );
}
else
{
if(!right) right = new Node();
return new Node( left, right->update(mid+1, dr, pos) );
}
}
} *aint[Nmax];
ll query(int st, int dr, Node *a, Node *b, int k)
{
if(k < 0) return -inf;
if(k > b->sz - a->sz) return b->sz - a->sz;
if(st == dr) return (ll) k * st;
ll sum = 0; int nr = 0;
if(!a->left) a->left = new Node();
if(!a->right) a->right = new Node();
if(!b->left) b->left = new Node();
if(!b->right) b->right = new Node();
sum += b->right->sum, nr += b->right->sz;
sum -= a->right->sum, nr -= a->right->sz;
if(nr >= k) return query(mid+1, dr, a->right, b->right, k);
else return sum + query(st, mid, a->left, b->left, k - nr);
}
void divide(int st, int dr, int L, int R)
{
ans[mid] = -inf; best[mid] = -1;
int i;
for(i=L; i<=R; ++i)
{
int rest = T - 2 * (K - mid) - (i - K);
ll res = query(0, lim, aint[mid], aint[i+1], rest);
if(res > ans[mid])
ans[mid] = res, best[mid] = i;
}
if(st <= mid-1) divide(st, mid-1, L, best[mid]);
if(mid+1 <= dr) divide(mid+1, dr, best[mid], R);
}
ll solve(int N, int _K, int _T, int A[])
{
K = _K; T = _T;
int i;
aint[0] = new Node();
for(i=1; i<=N; ++i)
{
aint[i] = aint[i-1];
aint[i] = aint[i] -> update(0, lim, A[i-1]);
}
divide(0, K, K, N-1);
ll Ans = 0;
for(i=0; i<N; ++i) Ans = max(Ans, ans[i]);
return Ans;
}
ll findMaxAttraction(int n, int start, int days, int A[])
{
int i, *B;
B = new int[n];
for(i=0; i<n; ++i) B[i] = A[n-1-i];
return max( solve(n, start, days, A), solve(n, n-1-start, days, B) );
}
