#include <bits/stdc++.h>

#define el '\n'
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef long double ld;

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

void testCase() {
    int n;
    cin >> n;

    int h[n];
    for (int i = 1; i < n; i++)
        cin >> h[i];

    int q;
    cin >> q;

    int a, b;
    vector<pair<int, int>> l[n + 1], r[n + 1];
    for (int i = 1; i <= q; i++) {
        cin >> a >> b;

        if (a < b)
            r[b - 1].emplace_back(a, i);
        else
            l[b].emplace_back(a - 1, i);
    }

    ll sol[q + 1];
    vector<int> v;
    vector<ll> sum;
    for (int i = 1; i < n; i++) {
        while (v.size() && h[v.back()] < h[i])
            v.pop_back(), sum.pop_back();

        sum.push_back((sum.size() ? sum.back() : 0) + 1LL * h[i] * (i - (v.size() ? v.back() : 0))), v.push_back(i);

        for (auto &j: r[i]) {
            int k = lower_bound(v.begin(), v.end(), j.first) - v.begin();

            sol[j.second] = sum.back() - sum[k];

            sol[j.second] += 1LL * h[v[k]] * (v[k] - j.first + 1);

            sol[j.second] += 1LL * h[v[k]] * (!k ? j.first - 1 : j.first - v[k - 1] - 1);
        }
    }

    v.clear(), sum.clear();
    for (int i = n - 1; i >= 1; i--) {
        while (v.size() && h[v.back()] < h[i])
            v.pop_back(), sum.pop_back();

        sum.push_back((sum.size() ? sum.back() : 0) + 1LL * h[i] * ((v.size() ? v.back() : n) - i)), v.push_back(i);

        for (auto &j: l[i]) {
            int s = 0, e = v.size() - 1, m, k;
            while (s <= e) {
                m = (s + e) >> 1;

                if (v[m] < j.first + 1)
                    e = m - 1, k = m;
                else
                    s = m + 1;
            }

            sol[j.second] = sum.back() - sum[k];

            sol[j.second] += 1LL * h[v[k]] * (j.first + 1 - v[k]);

            sol[j.second] += 1LL * h[v[k]] * (!k ? n - j.first - 1 : v[k - 1] - j.first - 1);
        }
    }

    for (int i = 1; i <= q; i++)
        cout << sol[i] << el;
}

signed main() {
    Beevo

    int t = 1;
//    cin >> t;

    while (t--)
        testCase();
}