#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const ll inf = numeric_limits<ll> :: max();
struct ST{
vector<ll> t;
int n;
void init(int ns){
n = ns;
t.assign(4 * n, inf);
}
void upd(int v, int tl, int tr, int& p, ll& k){
if (tl == tr){
t[v] = k;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (p <= tm){
upd(vv, tl, tm, p, k);
}
else {
upd(vv + 1, tm + 1, tr, p, k);
}
t[v] = min(t[vv], t[vv + 1]);
}
void upd(int p, ll k){
upd(1, 1, n, p, k);
}
ll get(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return inf;
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2, vv = 2 * v;
return min(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
}
ll get(int l, int r){
return get(1, 1, n, l, r);
}
};
vector<ll> minimum_costs(vector<int> A1, vector<int> L, vector<int> R){
int n = (int) A1.size(), q = (int) L.size();
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = A1[i - 1];
vector<int> log(n + 1);
for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
const int lg = log[n];
vector<vector<int>> sp(n + 1, vector<int>(lg + 1));
for (int i = 1; i <= n; i++) sp[i][0] = a[i];
for (int j = 1; j <= lg; j++){
for (int i = 1; i + (1 << j) <= n + 1; i++){
sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
auto get = [&](int l, int r){
if (l > r) swap(l, r);
int k = log[r - l + 1];
return max(sp[l][k], sp[r - (1 << k) + 1][k]);
};
vector<ll> ret;
map<int, vector<int>> d;
for (int i = 1; i <= n; i++) d[a[i]].pb(i);
vector<int> :: iterator it1, it2;
map<pii, ll> mp;
auto len = [&](int l, int r){
return (r - l + 1);
};
map<int, ST> T;
for (auto p: d){
T[p.ff].init((int) p.ss.size());
}
auto f = [&](int l, int r){
int mx = get(l, r);
it1 = lower_bound(d[mx].begin(), d[mx].end(), l);
it2 = upper_bound(d[mx].begin(), d[mx].end(), r); it2--;
ll out = 1LL * mx * len(l, r);
if (l < (*it1)) out = min(out, mp[{l, (*it1) - 1}] + 1LL * mx * (len(l, r) - len(l, (*it1) - 1)));
if ((*it2) < r) out = min(out, mp[{(*it2) + 1, r}] + 1LL * mx * (len(l, r) - len((*it2) + 1, r)));
int l1 = (int) (it1 - d[mx].begin()) + 1, r1 = (int) (it2 - d[mx].begin());
if (l1 <= r1){
out = min(out, T[mx].get(l1, r1) + 1LL * mx * len(l, r));
}
return out;
};
function<void(int, int)> build = [&](int l, int r){
int mx = get(l, r);
it1 = lower_bound(d[mx].begin(), d[mx].end(), l);
it2 = upper_bound(d[mx].begin(), d[mx].end(), r); it2--;
vector<pii> st;
vector<arr3> all;
if (l < (*it1)) st.pb({l, (*it1) - 1});
for (int i = (int) (it1 - d[mx].begin()); i < (int) (it2 - d[mx].begin()); i++){
st.pb({d[mx][i] + 1, d[mx][i + 1] - 1});
all.pb({d[mx][i] + 1, d[mx][i + 1] - 1, i});
}
if ((*it2) < r) st.pb({(*it2) + 1, r});
for (auto [l1, r1]: st) build(l1, r1);
for (int i = 0; i < st.size(); i++){
auto [l1, r1] = st[i];
for (int j = l1; j <= r1; j++){
mp[{l1, j}] = f(l1, j);
mp[{j, r1}] = f(j, r1);
}
}
for (auto [l1, r1, jj]: all){
T[mx].upd(jj + 1, mp[{l1, r1}] - 1LL * mx * len(l1, r1));
}
};
build(1, n);
for (int i = 0; i < q; i++){
int l, r; // cin>>l>>r;
l = L[i]; r = R[i];
l++; r++;
ret.pb(f(l, r));
}
return ret;
}
