#include <bits/stdc++.h>
#include"holiday.h"
#define pb push_back
using namespace std;
struct SegTree
{
int n;
vector<int> left, right;
vector<long long int> data;
SegTree(int n) : n(n), left(1, -1), right(1, -1), data(1, 0) {}
void expand(int index)
{
if (left[index] != -1)
return;
left[index] = data.size();
left.pb(-1), right.pb(-1), data.pb(0);
right[index] = data.size();
left.pb(-1), right.pb(-1), data.pb(0);
}
void change(int l, int r, int index, int i, int val)
{
if (i >= r || l > i)
return;
if (l + 1 == r)
{
data[index] += val;
return;
}
expand(index);
int m = l+r>>1;
change(l, m, left[index], i, val);
change(m, r, right[index], i, val);
data[index] = data[left[index]] + data[right[index]];
}
void change(int i, int val) { change(0, n, 0, i, val); }
long long int get(int l, int r, int index, int ss, int ee)
{
if (ss >= r || l >= ee || index == -1)
return 0;
if (ee >= r && l >= ss)
return data[index];
int m = l+r>>1;
long long int lres = get(l, m, left[index], ss, ee);
long long int rres = get(m, r, right[index], ss, ee);
return lres + rres;
}
long long int get(int ss, int ee) { return get(0, n, 0, ss, ee); }
};
int *v;
int n;
int start;
int d;
long long int subtask1()
{
return 0;
}
constexpr static int MXSIZE = 101;
long long int subtask2()
{
SegTree st1(MXSIZE);
SegTree st2(MXSIZE);
long long int best = 0;
for (int i = 0; i < n && i < d; i++)
{
st1.change(v[i], 1);
st2.change(v[i], v[i]);
int l = -1, r = MXSIZE;
while (r - l > 1)
{
int m = l+r>>1;
if (st1.get(m, n) + i < d)
r = m;
else
l = m;
}
long long int sum = st2.get(r, MXSIZE);
if (r != 0)
{
long long int remaining = d - st1.get(r, MXSIZE) - i;
sum += remaining * (r-1);
}
best = max(best, sum);
}
return best;
}
long long int findMaxAttraction(int nn, int sstart, int dd, int aattraction[]) {
n = nn;
start = sstart;
d = dd;
v = aattraction;
#ifndef DEBUGGING
if (n <= 3000)
return subtask1();
#endif
return subtask2();
}
