#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll linf = ll(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
typedef vector<ll> vll;
struct node
{
ll best=0, l, r;
ll value=0, split;
node *lc=0, *rc=0;
node(ll l, ll r) : l(l), r(r) {}
};
vll h;
int n;
node* build_tree(int l, int r)
{
if (l > r) return 0;
if (r < l) return 0;
node* ret = new node(l, r);
if (l==r)
{
ret->value = h[l];
ret->best = h[l];
ret->split = l;
return ret;
}
ll largest = 0;
repp(i, l, r + 1) largest = max(largest, h[i]);
ret->value = largest;
vll lindex;
repp(i, l, r + 1) if (h[i] == largest) lindex.push_back(i);
int split = lindex[sz(lindex) / 2];
ret->split = split;
ret->lc = build_tree(l, split - 1);
ret->rc = build_tree(split + 1, r);
ll lcost = (r - (split + 1) + 2) * largest;
if (ret->lc) lcost += ret->lc->best;
ll rcost = ((split - 1) - l + 2) * largest;
if (ret->rc) rcost += ret->rc->best;
ret->best = min(lcost, rcost);
return ret;
}
ll query(node* x, int ql, int qr)
{
if (!x) return linf;
if (x->l >= ql && x->r <= qr)
{
return x->best;
}
if (x->l > qr || x->r < ql) return linf;
return min((x->split-1-ql+2)*x->value+query(x->rc,ql,qr),
(qr-x->split-1+2)*x->value+query(x->lc,ql,qr));
}
ll solve(int l, int r)
{
if (l > r) return 0;
if (r < l) return 0;
if (l==r)
{
return h[l];
}
ll largest = 0;
repp(i, l, r + 1) largest = max(largest, h[i]);
ll ret = (r - l + 1) * largest;
vll lindex;
repp(i, l, r + 1) if (h[i] == largest) lindex.push_back(i);
int split = lindex[sz(lindex) / 2];
ll tot_len = r - l + 1;
ret = min(ret, (r - (split + 1) + 2) * largest + solve(l, split-1));
ret = min(ret, ((split - 1) - l + 2) * largest + solve(split + 1, r));
return ret;
}
vll minimum_costs(vi H, std::vector<int> L, std::vector<int> R)
{
h = vll(H.begin(), H.end());
n = sz(h);
node* root = build_tree(0, n - 1);
int q = sz(L);
vll ret(q);
rep(qu, q)
{
int l = L[qu];
int r = R[qu];
ret[qu] = query(root, l, r);
}
return ret;
}
