#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
const long long INF = 1LL << 60;
struct FirstKStructure {
set<pair<int, int> > data;
void insert(int x, int i) {
data.insert(make_pair(-x, i));
}
void erase(int x, int i) {
data.erase(make_pair(-x, i));
}
long long getFirstK(int k) {
int i = 0;
long long rez = 0LL;
for(auto it: data) {
if(i < k)
rez = rez - it.first;
i++;
}
return rez;
}
};
int *attraction;
bool twopointers(int n, int start, int d, long long cost) {
FirstKStructure *str = new FirstKStructure();
int l = 0;
for(int i = 0; i < start; ++i)
str->insert(attraction[i], i);
for(int r = start; r < n && l <= start; ++r) {
int k;
long long cost2;
str->insert(attraction[r], r);
do {
k = d - 2 * (r - start) - (start - l);
if(k < 0)
cost2 = -1;
else
cost2 = str->getFirstK(k);
if(cost2 < cost && k <= r - l + 1) {
str->erase(attraction[l], l);
++l;
} else if(cost2 >= cost)
return true;
} while(k <= r - l + 1 && l <= start && l <= r && cost2 < cost);
}
return false;
}
bool check(int n, int start, int d, long long cost) {
bool rez = false;
rez |= twopointers(n, start, d, cost);
reverse(attraction, attraction + n);
rez |= twopointers(n, n - start - 1, d, cost);
reverse(attraction, attraction + n);
return rez;
}
long long int findMaxAttraction(int n, int start, int d, int _attraction[]) {
long long st = 0LL, dr = INF;
attraction = _attraction;
while(dr - st > 1) {
long long mid = (st + dr) / 2;
if(check(n, start, d, mid))
st = mid;
else
dr = mid;
}
return st;
}
