#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 100100;
constexpr ll INF = 4e18;
int n, q;
int a[MAXN], L[MAXN], R[MAXN], C[MAXN];
vector<int> Q[MAXN];
ll ans[MAXN];
struct Seg{
pair<int, int> tree[MAXN*2];
int sz;
void init(int n, int a[]){
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], i-sz};
for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
int query(int l, int r){
++r;
pair<int, int> ret = {-1, -1};
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = max(ret, tree[l++]);
if (r&1) ret = max(ret, tree[--r]);
}
assert(ret.second!=-1);
return ret.second;
}
}tree, tree2;
struct Line{
ll a, b;
Line(){}
Line(ll _a, ll _b): a(_a), b(_b) {}
ll operator()(ll x){return a*x + b;}
};
ll cross(const Line &f, const Line &g){
assert(f.a > g.a);
ll ret = (g.b - f.b) / (f.a - g.a) + 1;
assert(ret <= n+1);
return ret;
}
struct DS{
deque<Line> L;
deque<int> p;
ll ofs;
void clear(){L.clear(); p.clear(); ofs = 0;}
void init(int x, int y){
assert(L.empty() && p.empty() && ofs==0);
L.emplace_back(0, y);
p.push_back(x);
p.push_back(x+1);
}
void push_front(ll a, ll b, int x){
L.emplace_front(a, b-ofs);
p.push_front(x);
}
void push_back(ll a, ll b, int x){
L.emplace_back(a, b-ofs);
p.push_back(x);
}
void add(ll x){ofs += x;}
void insert(ll a, ll b){
int s = p.front(); p.pop_front();
int e = p.back();
int prv = s;
Line f(a, b-ofs);
while(!L.empty()){
if (f(p.front()-1) > L.front()(p.front()-1)){
p.push_front(max((ll)prv, cross(f, L.front())));
p.push_front(s);
L.push_front(f);
return;
}
prv = p.front();
L.pop_front(); p.pop_front();
}
assert(L.empty() && p.empty());
L.push_front(f);
p.push_front(e);
p.push_front(s);
}
ll back(){return L.back()(p.back());}
int size(){return L.size();}
ll operator()(int x){
assert(p.front()<=x && x<p.back());
int idx = upper_bound(p.begin(), p.end(), x) - p.begin() - 1;
return L[idx](x) + ofs;
}
}D[MAXN];
void merge(int x, int y){
assert(D[x].p.back() + 1 == D[y].p.front());
if (D[x].size() >= D[y].size()){
int sz = D[y].size();
for (int i=0;i<sz;i++){
D[x].push_back(D[y].L[i].a, D[y].L[i].b + D[y].ofs, D[y].p[i+1]);
}
}
else{
swap(D[x], D[y]);
D[x].p.front()--;
int sz = D[y].size();
for (int i=sz-1;i>=0;i--){
D[x].push_front(D[y].L[i].a, D[y].L[i].b + D[y].ofs, D[y].p[i]);
}
}
}
void dnc(int l, int r){
if (l>r) return;
//printf("dnc: %d %d\n", l, r);
int m = tree.query(l, r);
dnc(l, m-1); dnc(m+1, r);
for (auto &i:Q[m]){
assert(L[i] <= m);
if (m < R[i]) ans[i] = min(ans[i], D[m+1](R[i]) + (ll)a[m] * (m-L[i]+1));
else if (m == R[i]) ans[i] = min(ans[i], (ll)a[m] * (m-L[i]+1));
else assert(0);
}
if (l==r){
D[l].init(l, a[l]);
}
else if (m==r){
D[l].push_back(0, D[l].back() + a[m], m+1);
}
else if (l==m){
D[m+1].add((ll)a[m] * (m-l+1));
D[m+1].insert(a[m], - (ll)a[m]*(m-1));
D[m+1].p.front()--;
assert(D[m+1].p.front()==m);
swap(D[m], D[m+1]);
}
else{
ll t = D[l].back();
D[m+1].add((ll)a[m] * (m-l+1));
D[m+1].insert(a[m], t - (ll)a[m]*(m-1));
merge(l, m+1);
}
//printf("end: %d %d\n", l, r);
}
int cnt;
void dnc0(int l, int r){
if (l>r) return;
//printf("dnc0: %d %d\n", l, r);
int m = tree.query(l, r);
C[m] = cnt--;
dnc0(l, m-1); dnc0(m+1, r);
}
void solve(vector<int> H, vector<int> _L, vector<int> _R){
for (int i=1;i<=n;i++){
a[i] = H[i-1];
Q[i].clear();
D[i].clear();
}
for (int i=1;i<=q;i++){
L[i] = _L[i-1] + 1;
R[i] = _R[i-1] + 1;
}
tree.init(n+1, a);
cnt = n;
dnc0(1, n);
tree2.init(n+1, C);
for (int i=1;i<=q;i++){
Q[tree2.query(L[i], R[i])].push_back(i);
}
dnc(1, n);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
n = H.size();
q = L.size();
fill(ans+1, ans+q+1, INF);
solve(H, L, R);
reverse(H.begin(), H.end());
for (auto &x:L) x = n-1-x;
for (auto &x:R) x = n-1-x;
solve(H, R, L);
vector<ll> rans;
for (int i=1;i<=q;i++) rans.push_back(ans[i]);
return rans;
}
