#include <bits/stdc++.h>

using i64 = long long;

template <typename T, typename Cmp = std::less<T>>
struct RMQ {
    const Cmp cmp;
    int n;
    std::vector<std::vector<T>> a;
    RMQ() = default;
    RMQ(const std::vector<T> &v) : cmp{} {
        init(v);
    }
    RMQ(const std::vector<T> &v, const Cmp &cmp_) : cmp{cmp_} {
        init(v);
    }
    void init(const std::vector<T> &ini) {
        n = int(ini.size());
        int lg = std::__lg(n);
        a.assign(lg + 1, std::vector<T>(n));
        a[0] = ini;
        for (int i = 0; i < lg; ++i) {
            for (int j = 0; j <= n - (2 << i); ++j) {
                a[i + 1][j] = std::min(a[i][j], a[i][j + (1 << i)], cmp);
            }
        }
    }
    T operator()(int l, int r) const {
        int k = std::__lg(r - l);
        return std::min(a[k][l], a[k][r - (1 << k)], cmp);
    }
};

template <typename Info, typename Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> s;
    std::vector<Tag> t;

    LazySegmentTree() = default;
    LazySegmentTree(int n_, const Info &v = Info{}) {
        init(n_, v);
    }
    template <typename T>
    LazySegmentTree(const std::vector<T> &v) {
        init(v);
    }
    void init(int n_, const Info &v = Info{}) {
        init(std::vector<Info>(n_, v));
    }
    template <typename T>
    void init(const std::vector<T> &v) {
        n = int(v.size());
        s.assign(4 << std::__lg(n), Info{});
        t.assign(4 << std::__lg(n), Tag{});
        auto build = [&](auto self, int u, int l, int r) -> void {
            if (r - l == 1) {
                s[u] = v[l];
                return;
            }
            int m = (l + r) / 2;
            self(self, u << 1, l, m);
            self(self, u << 1 | 1, m, r);
            pull(u);
        };
        build(build, 1, 0, n);
    }

    void pull(int u) {
        s[u] = s[u << 1] + s[u << 1 | 1];
    }
    void apply(int u, const Tag &v) {
        s[u].apply(v);
        t[u].apply(v);
    }
    void push(int u) {
        apply(u << 1, t[u]);
        apply(u << 1 | 1, t[u]);
        t[u] = Tag{};
    }

    void modify(int u, int l, int r, int p, const Info &v) {
        if (r - l == 1) {
            s[u] = v;
            return;
        }
        int m = (l + r) / 2;
        push(u);
        if (p < m) {
            modify(u << 1, l, m, p, v);
        } else {
            modify(u << 1 | 1, m, r, p, v);
        }
        pull(u);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }

    Info query(int u, int l, int r, int p) {
        if (p < l || r <= p) {
            return Info{};
        }
        if (r - l == 1) {
            return s[u];
        }
        int m = (l + r) / 2;
        push(u);
        if (p < m) {
            return query(u << 1, l, m, p);
        } else {
            return query(u << 1 | 1, m, r, p);
        }
    }
    Info query(int p) {
        return query(1, 0, n, p);
    }

    Info rangeQuery(int u, int l, int r, int ql, int qr) {
        if (qr <= l || r <= ql) {
            return Info{};
        }
        if (ql <= l && r <= qr) {
            return s[u];
        }
        int m = (l + r) / 2;
        push(u);
        return rangeQuery(u << 1, l, m, ql, qr) + rangeQuery(u << 1 | 1, m, r, ql, qr);
    }
    Info rangeQuery(int ql, int qr) {
        return rangeQuery(1, 0, n, ql, qr);
    }

    void rangeApply(int u, int l, int r, int ql, int qr, const Tag &v) {
        if (qr <= l || r <= ql) {
            return;
        }
        if (ql <= l && r <= qr) {
            apply(u, v);
            return;
        }
        int m = (l + r) / 2;
        push(u);
        rangeApply(u << 1, l, m, ql, qr, v);
        rangeApply(u << 1 | 1, m, r, ql, qr, v);
        pull(u);
    }
    void rangeApply(int ql, int qr, const Tag &v) {
        rangeApply(1, 0, n, ql, qr, v);
    }
};

struct Tag {
    bool v = false;
    i64 k = 1, b = 0;
    void apply(const Tag &rhs) {
        if (rhs.v) {
            *this = rhs;
        } else {
            std::tie(k, b) = std::pair{k * rhs.k, b * rhs.k + rhs.b};
        }
    }
};
struct Info {
    int l = -1, r = -1;
    i64 vl = 0, vr = 0;
    void apply(const Tag &rhs) {
        if (rhs.v) {
            vl = l;
            vr = r;
        }
        vl = vl * rhs.k + rhs.b;
        vr = vr * rhs.k + rhs.b;
    }
};
Info operator+(const Info &a, const Info &b) {
    return Info{a.l, b.r, a.vl, b.vr};
}

struct DS : LazySegmentTree<Info, Tag> {
    DS(int n, const Info &v = Info{}) : LazySegmentTree(n, v) {}
    void rangeUpdate(int u, int l, int r, int ql, int qr, const Tag &x, const Tag &y) {
        if (qr <= l || r <= ql) {
            return;
        }
        if (ql <= l && r <= qr) {
            Info vx = s[u], vy = s[u];
            vx.apply(x);
            vy.apply(y);
            if (vx.vl <= vy.vl && vx.vr <= vy.vr) {
                apply(u, x);
                return;
            }
            if (vy.vr <= vx.vr && vy.vl <= vx.vl) {
                apply(u, y);
                return;
            }
        }
        int m = (l + r) / 2;
        push(u);
        rangeUpdate(u << 1, l, m, ql, qr, x, y);
        rangeUpdate(u << 1 | 1, m, r, ql, qr, x, y);
        pull(u);
    }
    void rangeUpdate(int ql, int qr, const Tag &x, const Tag &y) {
        rangeUpdate(1, 0, n, ql, qr, x, y);
    }
};

std::vector<i64> minimum_costs(std::vector<int> a, std::vector<int> L, std::vector<int> R) {
    const int n = int(a.size()), q = int(L.size());

    std::vector<int> ord(n);
    std::iota(ord.begin(), ord.end(), 0);
    auto cmp = [&](int x, int y) {
        return std::tie(a[x], x) > std::tie(a[y], y);
    };
    RMQ rmq(ord, cmp);

    std::vector<std::vector<int>> qry(n);
    for (int i = 0; i < q; ++i) {
        int l = L[i], r = R[i], m = rmq(l, r + 1);
        qry[m].push_back(i);
    }

    std::vector<i64> ans(q);
    DS pre(n), suf(n);
    auto query = [&](int l, int m, int r) {
        i64 vl = suf.query(l).vl + 1ll * a[m] * (r - m + 1);
        i64 vr = pre.query(r).vl + 1ll * a[m] * (m - l + 1);
        return std::min(vl, vr);
    };
    auto solve = [&](auto self, int l, int r) -> i64 {
        if (l > r) {
            return 0;
        }
        int m = rmq(l, r + 1);
        i64 vl = self(self, l, m - 1);
        i64 vr = self(self, m + 1, r);
        i64 vm = std::min(vl + 1ll * a[m] * (r - m + 1), vr + 1ll * a[m] * (m - l + 1));
        for (auto id : qry[m]) {
            ans[id] = query(L[id], m, R[id]);
        }

        pre.rangeUpdate(m + 1, r + 1, Tag{true, a[m], vl + 1ll * a[m] * (-m + 1)}, Tag{false, 1, 1ll * a[m] * (m - l + 1)});
        pre.modify(m, Info{m, m, vl + a[m], vl + a[m]});
        suf.rangeUpdate(l, m, Tag{true, -a[m], vr + 1ll * a[m] * (m + 1)}, Tag{false, 1, 1ll * a[m] * (r - m + 1)});
        suf.modify(m, Info{m, m, vr + a[m], vr + a[m]});

        return vm;
    };
    solve(solve, 0, n - 1);

    return ans;
}