#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 750750;
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;
bool inv;
void init(int n, int a[], bool INV){
inv = INV;
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], inv?(sz-i):(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, 0};
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);
return inv?-ret.second: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;
}
template<typename T>
struct Deque{
vector<T> a;
int s, e, sz;
Deque(){s = e = sz = 0;}
void resize(){
if (a.empty()) a.resize(2);
else{
vector<T> b(a.size()*2);
int j = 0;
for (int i=s;i!=e;i++,j++){
if (i==(int)a.size()) i = 0;
b[j] = a[i];
}
swap(a, b);
s = 0;
e = j;
}
}
void push_front(T x){
if (sz>=(int)a.size()-1) resize();
--s;
if (s<0) s = (int)a.size()-1;
a[s] = x;
++sz;
}
void push_back(T x){
if (sz>=(int)a.size()-1) resize();
a[e] = x;
e++;
if (e==(int)a.size()) e = 0;
++sz;
}
void pop_front(){
s++;
if (s==(int)a.size()) s = 0;
--sz;
}
T front(){return a[s];}
void frontd(){a[s]--;}
T back(){
if (!e) return a.back();
return a[e-1];
}
T operator [](int x){
if (s+x<(int)a.size()) return a[s+x];
return a[s+x-(int)a.size()];
}
int size(){return sz;}
bool empty(){return sz == 0;}
void clear(){a.clear(); s = e = sz = 0;}
};
int _search(Deque<int> &dq, int target){
int l = 0, r = (int)dq.size()-1, ret = dq.size();
while(l<=r){
int m = (l+r)>>1;
if (target < dq[m]) r = m-1, ret = m;
else l = m+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.push_back(Line(0, y));
p.push_back(x);
p.push_back(x+1);
}
void push_front(ll a, ll b, int x){
L.push_front(Line(a, b-ofs));
p.push_front(x);
}
void push_back(ll a, ll b, int x){
L.push_back(Line(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()-1) + ofs;}
int size(){return L.size();}
ll operator()(int x){
assert(p.front()<=x && x<p.back());
int idx = _search(p, x) - 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.frontd();
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;
int m = tree.query(l, r);
//printf("dnc: %d %d (mid = %d)\n", l, r, m);
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.frontd();
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("\nDS %d %d (mid = %d)\n", l, r, m);
for (int i=0;i<D[l].L.size();i++) {auto [a, b] = D[l].L[i]; printf(" (%lld, %lld)", a, b+D[l].ofs);}
printf("\n");
for (int i=0;i<D[l].p.size();i++) printf(" %d", D[l].p[i]);
printf("\n");
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, bool INV){
/*printf("-------------------------------\n");
for (auto &x:H) printf(" %d", x);
printf("\n");*/
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, INV);
cnt = n;
dnc0(1, n);
tree2.init(n+1, C, INV);
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, 0);
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, 1);
vector<ll> rans;
for (int i=1;i<=q;i++) rans.push_back(ans[i]);
return rans;
}
