#include "meetings.h"
#include <bits/stdc++.h>
#define printf(...)
#define puts(...)
using namespace std;
typedef long long ll;
int n, q;
ll arr[7502];
int ql[7502], qr[7502];
ll ans[7502];
void solve();
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
n = (int)H.size();
for(int i=1; i<=n; i++) arr[i] = H[i-1];
q = (int)L.size();
for(int i=1; i<=q; i++) ql[i] = L[i-1]+1, qr[i] = R[i-1]+1, ans[i] = LLONG_MAX;
solve();
vector<ll> ret;
for(int i=1; i<=q; i++) ret.push_back(ans[i]);
return ret;
}
void makeCartesianTree();
void reformQuery();
void calculateAnswer();
int mult = 1;
void solve(){
makeCartesianTree();
reformQuery();
calculateAnswer();
reverse(arr+1, arr+n+1);
for(int i=1; i<=q; i++) ql[i] = n+1-ql[i], qr[i] = n+1-qr[i], swap(ql[i], qr[i]);
mult = -1;
makeCartesianTree();
reformQuery();
calculateAnswer();
}
struct segTree{
pair<ll, int> tree[1<<21];
void init(int i, int l, int r, ll *A){
if(l==r){
tree[i] = make_pair(A[l], l * mult);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
pair<int, int> query(int i, int l, int r, int s, int e){
if(r<s || e<l) return make_pair(0, 0);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int par[7502], lc[7502], rc[7002];
int intvL[7002], intvR[7502], root;
int thisL[7502];
int dnc(int l, int r, int p=0){
if(l>r) return 0;
int x = mult * tree.query(1, 1, n, l, r).second;
par[x] = p;
intvL[x] = l, intvR[x] = r;
lc[x] = dnc(l, x-1);
rc[x] = dnc(x+1, r);
thisL[intvL[x]] = x;
printf("thisL[%d] = %d\n", intvL[x], x);
return x;
}
void makeCartesianTree(){
for(int i=1; i<=n; i++){
par[i] = lc[i] = rc[i] = thisL[i] = 0;
}
tree.init(1, 1, n, arr);
root = dnc(1, n);
}
vector<int> vec[7502];
void reformQuery(){
for(int i=1; i<=n; i++) vec[i].clear();
for(int i=1; i<=q; i++){
if(ql[i] == qr[i]){
ans[i] = arr[i];
continue;
}
int l = ql[i], r = qr[i], x = mult * tree.query(1, 1, n, l, r).second;
if(x==n) ans[i] = min(ans[i], arr[x] * (r-l+1));
else vec[thisL[x+1]].push_back(i);
printf("Pushed %d to %d (x %d)\n", i, thisL[x+1], x);
}
}
struct Container{
struct Segment{
int l, r; ll a, b;
Segment(){}
Segment(int l, int r, ll a, ll b): l(l), r(r), a(a), b(b){}
};
ll lazy;
deque<Segment> vec;
Container(){
lazy = 0;
vec.clear();
}
void clear(){
lazy = 0;
vec.clear();
}
bool empty(){
return vec.empty();
}
void swap(Container &r){
::swap(lazy, r.lazy);
::swap(vec, r.vec);
}
void push_back(ll x, ll v){
vec.push_back(Segment(x, x, 0, v-lazy));
}
ll back(){
Segment p = vec.back();
return p.a*p.r+p.b+lazy;
}
void operator+=(Container &nxt){
if(vec.size() > nxt.vec.size()){
for(Segment &p: nxt.vec){
vec.push_back(p);
vec.back().b += nxt.lazy - lazy;
}
nxt.clear();
}
else{
for(int i=(int)vec.size()-1; i>=0; i--){
nxt.vec.push_front(vec[i]);
nxt.vec.front().b += lazy - nxt.lazy;
}
vec.clear();
swap(nxt);
}
}
void operator+=(ll &x){
lazy+=x;
}
void render(ll a, ll b){
if(vec[0].a * vec[0].l + vec[0].b + lazy <= a * vec[0].l + b) return; /// 바꿀 게 없음
ll lmost = vec[0].l, rmost = -1;
while(!vec.empty()){
Segment p = vec.front();
if(p.a*p.r+p.b+lazy >= a*p.r+b){
rmost = p.r;
vec.pop_front();
continue;
}
ll x = p.l - 1;
while(x<p.r && p.a*(x+1)+p.b+lazy > a*(x+1)+b) x++;
rmost = x-1;
vec.front().l = x;
break;
x = ceil((long double)(p.b+lazy-b) / (long double)(a - p.a));
rmost = x-1;
vec.front().l = x;
break;
}
vec.push_front(Segment(lmost, rmost, a, b-lazy));
}
ll get(ll x){
int L = 0, R = (int)vec.size();
while(L<R){
int M = (L+R)/2;
if(vec[M].r < x) L = M+1;
else R = M;
}
return vec[L].a * x + vec[L].b + lazy;
}
} DP[750002];
void dnc(int x){
int L = intvL[x], R = intvR[x];
printf("dnc %d %d %d\n", x, L, R);
/// [L, x]
if(lc[x]){
dnc(lc[x]), DP[x].swap(DP[lc[x]]);
DP[x].push_back(x, DP[x].back()+arr[x]);
}
else DP[x].push_back(x, arr[x]);
if(rc[x]){
dnc(rc[x]);
/// DP[rc[x]] 앞부분을 다듬는다
ll v = DP[x].back(), vAll = arr[x] * (x-L+1);
DP[rc[x]] += vAll;
DP[rc[x]].render(arr[x], v - arr[x] * x);
DP[x] += DP[rc[x]];
}
for(int idx: vec[x]){
ans[idx] = min(ans[idx], DP[x].get(qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
//printf("Checking %d: maybe %lld + %lld = %lld\n", idx, DP[x].get(qr[idx]), arr[intvL[x]-1]*(intvL[x]-ql[idx]),
// DP[x].get(qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
}
printf("Container[%d]\n", x);
for(Container::Segment p: DP[x].vec) printf("(%lld, %lld) - %lldx + %lld, \t", p.l, p.r, p.a, p.b + DP[x].lazy);
puts("");
}
void calculateAnswer(){
for(int i=1; i<=n; i++) DP[i].clear();
dnc(root);
}
