#include "meetings.h"
#include <bits/stdc++.h>
#define m first
#define c second
using namespace std;
typedef pair<long long, long long> ii;
typedef pair<long long, long long> line;
const int MAXN = 750005;
const long long INF = 10234567890123456;
int n, Q;
static long long H[MAXN];
struct query {long long l, r, id;};
static vector<query> queries[MAXN];
struct segmenttree{
ii tree[MAXN*2];
void init(){
for(int i = 0;i < n;i++) tree[i+n]= ii(H[i],i);
for(int i = n-1;i >= 1;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
int query(int l, int r){
ii res = ii(0,0);
for(l += n, r += n+1;l < r;l >>= 1, r >>= 1){
if(l&1) res = max(res, tree[l++]);
if(r&1) res = max(res, tree[--r]);
}
return res.second;
}
} FINDMAX;
long long get(line L, long long x) { return L.m * x + L.c; }
struct lichao{
int s, e, m;
lichao *l, *r;
line val = {0,INF};
long long lazy = 0;
lichao(int S, int E){
s = S, e = E, m = (s+e)/2;
if(s != e){
l = new lichao(s,m);
r = new lichao(m+1,e);
}
}
void push(){
if(s == e) return;
l->lazy += lazy;
r->lazy += lazy;
(l->val).c += lazy;
(r->val).c += lazy;
lazy = 0;
}
/*
void insert(line L){
//push();
if(get(L, m+1) < get(val, m+1)) swap(val, L);
if(s == e) return;
if(get(L,s) < get(val,s)) l->insert(L);
else r->insert(L);
}
*/
void findInsert(int S, int E, line L){
if(s > E || S > e || S > E) return;
push();
if(S <= s && e <= E){
if(get(val,s) > get(L,s)) swap(val, L);
if(s == e) return;
if(get(val,m) <= get(L,m)) r->findInsert(S, E, L);
else{
swap(val, L);
l->findInsert(S, E, L);
}
}
l->findInsert(S, E, L);
r->findInsert(S, E, L);
}
void lazyAdd(int S, int E, long long V){
push();
if(s == S && e == E){
lazy += V;
val.c += V;
return;
}
else if(E <= m) l->lazyAdd(S,E,V);
else if(S >= m+1) r->lazyAdd(S,E,V);
else{
l->lazyAdd(S,m,V);
r->lazyAdd(m+1,E,V);
}
}
long long query(long long x){
push();
if(s == e) return get(val,x);
if(x <= m) return min(get(val,x), l->query(x));
else return min(get(val,x), r->query(x));
}
} *Left, *Right;
vector<long long> ans;
void solve(long long L, long long R){
if(L > R) return;
long long M = FINDMAX.query(L, R);
solve(L,M-1);
solve(M+1,R);
Left->findInsert(M, M, line(0,0));
Right->findInsert(M, M, line(0,0));
for(query q : queries[M]){
ans[q.id] = min(Left->query(q.l) + (q.r - M + 1LL) * H[M],
Right->query(q.r) + (M - q.l + 1LL) * H[M]);
}
Left->lazyAdd(L, M, (R - M + 1) * H[M]); ///meeting place left of M
Left->findInsert(L, M, line(-H[M], (M+1) * H[M] + (R == M ? 0LL : Left->query(M+1) )) ); ///meeting place right of M
Right->lazyAdd(M, R, (M - L + 1) * H[M]); ///meeting place right of M
Right->findInsert(M, R, line(H[M], (1-M) * H[M] + (L == M ? 0LL : Right->query(M-1) )) );///meething place left of M
}
vector<long long> minimum_costs(vector<int> _H, vector<int> L, vector<int> R){
n = _H.size();
for(int i = 0;i < n;i++) H[i] = _H[i];
Q = L.size();
ans.resize(Q);
FINDMAX.init();
for(int i = 0;i < Q;i++){
int m = FINDMAX.query(L[i],R[i]);
queries[m].push_back({L[i],R[i],i});
}
Left = new lichao(0,n-1);
Right = new lichao(0,n-1);
solve(0, n-1);
return ans;
}
