#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
int n, q;
vector<pair<int, int>>query;
vector<int>a;
namespace sub12{
vector<ll>solve(){
vector<vector<ll>>f(n + 1, vector<ll>(n + 1));
for(int i = 1; i <= n; i++){
f[i][0] = 0;
for(int j = 1; j < i; j++){
f[i][j] += f[i][j - 1];
}
for(int j = i, x = 0; j <= n; j++){
maximize(x, a[j]);
f[i][j] = f[j][i] = x;
f[i][j] += f[i][j - 1];
}
}
vector<ll>ans;
for(auto& [l, r] : query){
ll cur = INF;
for(int i = l; i <= r; i++){
minimize(cur, f[i][r] - f[i][l - 1]);
}
ans.push_back(cur);
}
return ans;
}
}
namespace sub3{
struct Node{
int len, pf, sf, opt;
Node(){
len = pf = sf = opt = 0;
}
};
Node merge(Node a, Node b){
Node c;
c.len = a.len + b.len;
c.pf = a.pf == a.len ? a.pf + b.pf : a.pf;
c.sf = b.sf == b.len ? b.sf + a.sf : b.sf;
c.opt = max({a.opt, b.opt, a.sf + b.pf});
return c;
}
vector<ll>solve(){
vector<Node>st(n << 2 | 3);
function<void(int, int, int)>build;
build = [&] (int id, int l, int r){
if(l == r){
st[id].pf = st[id].sf = st[id].opt = a[l] & (st[id].len = 1);
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
st[id] = merge(st[id << 1], st[id << 1 | 1]);
};
build(1, 1, n);
function<Node(int, int, int, int, int)>get;
get = [&] (int id, int l, int r, int u, int v){
if(l > v || r < u){
return Node();
}
if(u <= l && v >= r){
return st[id];
}
int m = (l + r) >> 1;
return merge(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
};
vector<ll>ans;
for(auto& [l, r] : query){
ans.push_back(((r - l + 1) << 1) - get(1, 1, n, l, r).opt);
}
return ans;
}
}
namespace sub4{
struct Node{
int l, r, m, lc, rc;
ll v;
Node(){}
};
vector<Node>st(1);
int build(int l, int r){
if(l > r){
return 0;
}
int id = st.size();
st.push_back(Node());
st[id].l = l;
st[id].r = r;
if(l < r){
int mx = *max_element(a.begin() + l, a.begin() + r + 1);
vector<int>p;
for(int i = l; i <= r; i++){
if(a[i] == mx){
p.push_back(i);
}
}
st[id].m = p[int(p.size()) >> 1];
st[id].v = min(st[st[id].lc = build(l, st[id].m - 1)].v + ll(mx) * (r - st[id].m + 1), st[st[id].rc = build(st[id].m + 1, r)].v + ll(mx) * (st[id].m - l + 1));
}
else{
st[id].v = a[l];
}
return id;
}
int overlap(int l1, int r1, int l2, int r2){
return max(0, min(r1, r2) - max(l1, l2) + 1);
}
ll get(int id, int u, int v){
if(st[id].l > v || st[id].r < u){
return 0;
}
if(u <= st[id].l && v >= st[id].r){
return st[id].v;
}
return min(get(st[id].lc, u, v) + ll(a[st[id].m]) * overlap(st[id].m, st[id].r, u, v), get(st[id].rc, u, v) + ll(a[st[id].m]) * overlap(st[id].l, st[id].m, u, v));
}
vector<ll>solve(){
build(1, n);
vector<ll>ans;
for(auto& [l, r] : query){
ans.push_back(get(1, l, r));
}
return ans;
}
}
namespace sub5{
const int lim = 75e4 + 5;
int lgv[lim], spt[20][lim];
bool flag = false;
struct Node{
int l, r, p, lc, rc;
Node(){
lc = rc = -1;
}
};
int max_index(int i, int j){
if((!flag && i > j) || (flag && i < j)){
swap(i, j);
}
return a[i] > a[j] ? i : j;
}
int get_max_pos(int l, int r){
int k = lgv[r - l + 1];
return max_index(spt[k][l], spt[k][r - (1 << k) + 1]);
}
vector<Node>st;
int build(int l, int r){
if(l > r){
return -1;
}
int id = st.size();
st.push_back(Node());
st[id].lc = build(l, (st[id].p = get_max_pos(st[id].l = l, st[id].r = r)) - 1);
st[id].rc = build(st[id].p + 1, r);
return id;
}
vector<int>event[lim];
vector<ll>ans;
struct SegmentTree{
ll st[lim << 2], lazy[lim << 2];
bitset<lim << 2>mark;
void init(){
memset(st, 0, sizeof(st));
memset(lazy, 0, sizeof(lazy));
mark.reset();
}
void propagate(int id, ll x){
st[id] += x;
lazy[id] += x;
}
void push_down(int id){
if(mark[id]){
mark[id << 1] = mark[id << 1 | 1] = true;
st[id << 1] = st[id << 1 | 1] = lazy[id << 1] = lazy[id << 1 | 1] = 0;
mark[id] = false;
}
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, ll x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = st[id << 1 | 1];
}
void fill_zero(int id, int l, int r, int u, int v){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
mark[id] = true;
st[id] = lazy[id] = 0;
return;
}
int m = (l + r) >> 1;
push_down(id);
fill_zero(id << 1, l, m, u, v);
fill_zero(id << 1 | 1, m + 1, r, u, v);
st[id] = st[id << 1 | 1];
}
ll get(int p){
int id = 1, l = 0, r = n;
while(l < r){
int m = (l + r) >> 1;
push_down(id);
id <<= 1;
if(m < p){
id |= 1;
l = m + 1;
}
else{
r = m;
}
}
return st[id];
}
};
struct SegmentTreeLine{
SegmentTree a, b;
void init(){
a.init();
b.init();
}
void update(int u, int v, pair<int, ll>line){
a.update(1, 0, n, u, v, line.first);
b.update(1, 0, n, u, v, line.second - ll(u) * line.first);
}
void fill_zero(int u, int v){
a.fill_zero(1, 0, n, u, v);
b.fill_zero(1, 0, n, u, v);
}
ll get(int p){
return a.get(p) * p + b.get(p);
}
int walk(int id, int l, int r, int u, int v, int mx, ll f, ll g){
if(r < u){
return r;
}
if(l > v){
return l - 1;
}
if(u <= l && v >= r && f + ll(mx) * (r - u + 1) < g + a.st[id] * r + b.st[id]){
return r;
}
if(l == r){
return l - 1;
}
int m = (l + r) >> 1;
a.push_down(id);
b.push_down(id);
int left = walk(id << 1, l, m, u, v, mx, f, g);
return left == m ? walk(id << 1 | 1, m + 1, r, u, v, mx, f, g) : left;
}
};
SegmentTreeLine val;
void dfs(int id){
if(st[id].lc != -1){
dfs(st[id].lc);
}
if(st[id].rc != -1){
dfs(st[id].rc);
}
val.update(st[id].p, st[id].p, make_pair(0, val.get(st[id].p - 1) + a[st[id].p]));
if(st[id].rc != -1){
int pos = val.walk(1, 0, n, st[id].p + 1, st[id].r, a[st[id].p], val.get(st[id].p), ll(st[id].p - st[id].l + 1) * a[st[id].p]);
val.fill_zero(st[id].p + 1, pos);
val.update(st[id].p + 1, pos, make_pair(a[st[id].p], val.get(st[id].p) + a[st[id].p]));
val.update(pos + 1, st[id].r, make_pair(0, ll(st[id].p - st[id].l + 1) * a[st[id].p]));
}
for(int& i : event[st[id].p]){
minimize(ans[i], val.get(query[i].second) + ll(st[id].l - query[i].first) * a[st[id].l - 1]);
}
}
void play(){
for(int i = 1; i < 20; i++){
for(int j = 1; j + (1 << i) - 1 <= n; j++){
spt[i][j] = max_index(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
}
}
for(int i = 1; i <= n; i++){
event[i].clear();
}
for(int i = 0; i < q; i++){
auto& [l, r] = query[i];
int p = get_max_pos(l, r);
if(p < r){
event[get_max_pos(p + 1, r)].push_back(i);
}
else{
minimize(ans[i], ll(a[p]) * (r - l + 1));
}
}
val.init();
st.clear();
dfs(build(1, n));
}
vector<ll>solve(){
lgv[0] = -1;
for(int i = 1; i <= n; i++){
lgv[spt[0][i] = i] = lgv[i >> 1] + 1;
}
ans.assign(q, INF);
play();
flag = true;
reverse(a.begin() + 1, a.end());
for(auto& [l, r] : query){
swap(l = n - l + 1, r = n - r + 1);
}
play();
return ans;
}
}
vector<ll>minimum_costs(vector<int>H, vector<int>L, vector<int>R) {
q = L.size();
for(int i = 0; i < q; i++){
query.push_back(make_pair(L[i] + 1, R[i] + 1));
}
swap(a, H);
n = a.size();
a.insert(a.begin(), 0);
if(max(n, q) <= 5000){
return sub12::solve();
}
if(*max_element(a.begin() + 1, a.end()) <= 2){
return sub3::solve();
}
if(max(n, q) <= 100000 && *max_element(a.begin() + 1, a.end()) <= 20){
return sub4::solve();
}
return sub5::solve();
}
