#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "meetings.h"
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 1e5 + 5;
const int maxh = 21;
int n, q;
vector<int> h;
vector<int> o[maxh];
struct node
{
int l, r;
int nl, nr;
ll ans;
node()
{
l = -1, r = -1, nl = -1, nr = -1, ans = 0;
}
} v[maxn];
int build(int l, int r) // vrati cislo vrchola kde sa postavil
{
if (r < l) return n;
int mx = -1;
for (int i = maxh - 1; i >= 0; i--)
{
int lo = lower_bound(o[i].begin(), o[i].end(), l) - o[i].begin();
if (lo != o[i].size() && o[i][lo] <= r)
{
int up = upper_bound(o[i].begin(), o[i].end(), r) - o[i].begin() - 1;
mx = o[i][(lo + up) / 2];
break;
}
}
v[mx].l = l, v[mx].r = r;
v[mx].nl = build(l, mx - 1), v[mx].nr = build(mx + 1, r);
v[mx].ans = min((mx - l + 1) * 1ll * h[mx] + v[v[mx].nr].ans, (r - mx + 1) * 1ll * h[mx] + v[v[mx].nl].ans);
return mx;
}
ll query(int l, int r, int vr)
{
if (vr == n || r < v[vr].l || l > v[vr].r)
return 0;
if (l <= v[vr].l && v[vr].r <= r) return v[vr].ans;
if (r < vr) return query(l, r, v[vr].nl);
if (l > vr) return query(l, r, v[vr].nr);
ll ansl = query(l, r, v[vr].nl);
ll ansr = query(l, r, v[vr].nr);
return min(ansl + h[vr] * 1ll * (min(v[vr].r, r) - vr + 1), ansr + h[vr] * 1ll * (vr - max(v[vr].l, l) + 1));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
n = H.size();
h = H;
for (int i = 0; i < n; i++) o[h[i]].push_back(i);
int root = build(0, n - 1);
vector<ll> ans;
for (int i = 0; i < L.size(); i++)
{
ans.push_back(query(L[i], R[i], root));
}
return ans;
}
