/*
Code for problem C by cookiedoth
Generated 11 Sep 2020 at 10.19 PM
СТРОИМ СТЕНУ РАБОТЯГИ!
█▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█
z_z
>_<
¯\_(ツ)_/¯
*/
#include "meetings.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#include <utility>
#include <tuple>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)(a).size()
#pragma GCC optimize("Ofast")
using namespace std;
template<class T> int chkmax(T &a, T b) {
if (b > a) {
a = b;
return 1;
}
return 0;
}
template<class T> int chkmin(T &a, T b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
while (begin != end) {
out << (*begin) << " ";
begin++;
}
out << endl;
}
template<class T> void output(T x, ostream& out = cerr) {
output(x.begin(), x.end(), out);
}
void fast_io() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct rmq {
vector<pair<ll, int> > t;
int n0, n, idx_sign;
rmq() {}
void build(ll *h, int v, int tl, int tr) {
if (tl == tr) {
if (tl < n0) {
t[v] = {h[tl], tl * idx_sign};
}
} else {
int tm = (tl + tr) >> 1;
build(h, v * 2, tl, tm);
build(h, v * 2 + 1, tm + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
}
rmq(ll *h, int _n, int _idx_sign) {
n0 = _n;
n = 1;
while (n < _n) {
n <<= 1;
}
t.resize(2 * n);
idx_sign = _idx_sign;
build(h, 1, 0, n - 1);
}
pair<ll, int> get(int l, int r) {
pair<ll, int> res = {-1, -1};
l += n;
r += n;
while (l <= r) {
if (l & 1) {
res = max(res, t[l++]);
}
if ((r & 1) == 0) {
res = max(res, t[r--]);
}
l >>= 1;
r >>= 1;
}
res.second *= idx_sign;
return res;
}
};
struct fenwick {
fenwick() {}
vector<ll> t;
int n;
fenwick(int _n) {
n = _n;
t.resize(n);
}
void add(int pos, ll val) {
while (pos < n) {
t[pos] += val;
pos = pos | (pos + 1);
}
}
ll get(int pos) {
ll res = 0;
while (pos >= 0) {
res += t[pos];
pos = (pos & (pos + 1)) - 1;
}
return res;
}
};
struct superfenwick {
superfenwick() {}
fenwick F;
superfenwick(int _n) {
F = fenwick(_n + 1);
}
void add(int l, int r, ll val) {
F.add(l, val);
F.add(r + 1, -val);
}
ll get(int pos) {
return F.get(pos);
}
};
struct query {
int l, r, id;
};
const ll INF = 1e18 + 228;
const int mx = 8e5 + 228;
int n, q;
ll h[mx], ans[mx];
vector<vector<query> > Q_by_argmax;
vector<query> Q;
rmq T;
superfenwick F;
struct segment {
int start;
ll a, b;
ll get(int pos) {
return a + b * pos;
}
segment(int _start, ll _a, ll _b): start(_start), a(_a), b(_b) {}
};
bool operator < (const segment &a, const segment &b) {
return a.start < b.start;
}
void print(deque<segment> *d, int l, int r) {
cerr << "print " << l << " " << r << endl;
for (int i = 0; i < length(*d); ++i) {
int R = (i == length(*d) - 1 ? r : (*d)[i + 1].start - 1);
// cerr << "segment " << (*d)[i].start << ' ' << R << '\n';
for (int j = (*d)[i].start; j <= R; ++j) {
cerr << (*d)[i].a + (*d)[i].b * j + F.get(j) << ' ';
}
}
cerr << '\n';
}
deque<segment>* go(int l, int r) {
if (l > r) {
return new deque<segment> ();
}
if (l == r) {
deque<segment>* cur = new deque<segment> ();
cur->emplace_back(l, h[l], 0);
for (auto query : Q_by_argmax[l]) {
chkmin(ans[query.id], h[l]);
}
return cur;
}
int pos = T.get(l, r).second;
ll H = h[pos];
auto d1 = go(l, pos - 1);
auto d2 = go(pos + 1, r);
// cerr << "================merge " << l << " " << r << endl;
// cerr << "H = " << H << endl;
// if (!d1->empty()) {
// print(d1, l, pos - 1);
// }
// if (!d2->empty()) {
// print(d2, pos + 1, r);
// }
ll pos_val = (d1->empty() ? 0 : d1->back().get(pos - 1) + F.get(pos - 1)) + h[pos];
// cerr << "pos_val = " << pos_val << endl;
for (auto query : Q_by_argmax[pos]) {
if (query.r == pos) {
chkmin(ans[query.id], H * (pos - query.l + 1));
} else {
segment to_seach = {query.r, 0, 0};
int d2_pos = upper_bound(d2->begin(), d2->end(), to_seach) - 1 - d2->begin();
chkmin(ans[query.id], (*d2)[d2_pos].get(query.r) + F.get(query.r) + H * (pos - query.l + 1));
// cerr << H * (pos - query.l + 1) << endl;
// cerr << "kek " << ans[query.id] << endl;
}
}
d1->emplace_back(pos, pos_val, 0);
if (pos + 1 <= r) {
ll f1 = pos_val;
ll f2 = H * (pos - l + 1);
while (!d2->empty()) {
int back_pos = (d2->size() > 1 ? (*d2)[1].start - 1 : r);
ll mod = F.get(back_pos);
// cerr << "check " << back_pos << endl;
// cerr << (*d2)[0].get(back_pos) + mod + f2 << endl;
// cerr << f1 + H * (back_pos - pos) << endl;
// cerr << "f2 = " << f2 << endl;
if ((*d2)[0].get(back_pos) + mod + f2 <= f1 + H * (back_pos - pos)) {
// cerr << "opa back_pos = " << back_pos << endl;
// cerr << "back_res = " << f1 + H * (back_pos - pos) << endl;
// cerr << "back_res_opt = " << (*d2)[0].get(back_pos) + mod + f2 << endl;
// cerr << "f1 = " << f1 << endl;
// cerr << "pos = " << pos << endl;
// cerr << "H = " << H << endl;
// cerr << "a = " << (*d2)[0].a << endl;
// cerr << "mod = " << mod << endl;
// cerr << "b = " << (*d2)[0].b << endl;
// cerr << "LR = " << (*d2)[0].start << " " << back_pos << endl;
// cerr << "f2 = " << f2 << endl;
ll div1 = (*d2)[0].a + mod + f2 - f1 + H * pos;
ll div2 = (H - (*d2)[0].b);
int threshold;
if (div2 == 0) {
threshold = (*d2)[0].start;
} else {
threshold = (div1 + div2 - 1) / div2;
}
// cerr << "threshold = " << threshold << endl;
chkmax(threshold, (*d2)[0].start);
assert(threshold <= back_pos);
F.add((*d2)[0].start, threshold - 1, -mod);
(*d2)[0].start = threshold;
F.add(threshold, r, f2);
if (threshold > pos + 1) {
d2->push_front({pos + 1, f1 - H * pos, H});
}
// cerr << "opa " << (*d2)[0].start << endl;
// cerr << "kek " << (*d2)[1].start << endl;
// cerr << d2->size() << endl;
break;
} else {
F.add((*d2)[0].start, back_pos, -mod);
d2->pop_front();
}
}
if (d2->empty()) {
d2->push_front({pos + 1, f1 - H * pos, H});
}
}
if (d1->size() > d2->size()) {
for (auto x : (*d2)) {
d1->push_back(x);
}
delete d2;
// print(d1, l, r);
return d1;
} else {
for (int i = (int)d1->size() - 1; i >= 0; --i) {
d2->push_front((*d1)[i]);
}
delete d1;
// print(d2, l, r);
return d2;
}
}
void solve(int idx_sign) {
// cerr << "solve " << idx_sign << endl;
F = superfenwick(n);
Q_by_argmax.assign(n, vector<query> ());
T = rmq(h, n, idx_sign);
for (int i = 0; i < q; ++i) {
Q_by_argmax[T.get(Q[i].l, Q[i].r).second].push_back(Q[i]);
}
go(0, n - 1);
// cerr << ans[0] << endl;
}
void flip() {
reverse(h, h + n);
for (int i = 0; i < q; ++i) {
Q[i].l = n - 1 - Q[i].l;
Q[i].r = n - 1 - Q[i].r;
swap(Q[i].l, Q[i].r);
}
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
n = H.size();
q = L.size();
for (int i = 0; i < q; ++i) {
Q.push_back({L[i], R[i], i});
}
for (int i = 0; i < n; ++i) {
h[i] = H[i];
}
fill(ans, ans + q, INF);
solve(1);
flip();
solve(-1);
return vector<ll> (ans, ans + q);
}
