#include<iostream>
#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 5, M = 18, mod = 998244353;
int n, a[N];
pair<ll, int> dp1[N][M], dp2[N][M];

void preprocess() {
    stack<int> st;
    for (int i = n - 1; i >= 1; i--) {
        while (!st.empty() && a[st.top()] < a[i])st.pop();
        int nxt = st.empty() ? n : st.top();
        st.push(i);
        dp1[i][0] = {1ll * (nxt - i) * a[i], nxt};
        for (int j = 1; j < M; j++) {
            int nxt = dp1[i][j - 1].second;
            if (nxt) {
                dp1[i][j] = make_pair(dp1[i][j - 1].first + dp1[nxt][j - 1].first, dp1[nxt][j - 1].second);
            }
        }
    }

    while (!st.empty())st.pop();

    for (int i = 1; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i])st.pop();
        int nxt = st.empty() ? 0 : st.top();
        st.push(i);
        dp2[i][0] = {1ll * (i - nxt) * a[i], nxt};
        for (int j = 1; j < M; j++) {
            int nxt = dp2[i][j - 1].second;
            if (nxt) {
                dp2[i][j] = make_pair(dp2[i][j - 1].first + dp2[nxt][j - 1].first, dp2[nxt][j - 1].second);
            }
        }
    }
}

ll solve1(int l, int r) {
    ll ans = 0;
    for (int j = M - 1; j >= 0; j--) {
        if (dp1[l][j].second && dp1[l][j].second <= r) {
            ans += dp1[l][j].first;
            l = dp1[l][j].second;
        }
    }
    return ans + 1ll * (r - l + 1) * a[l];
}

ll solve2(int l, int r) {
    ll ans = 0;
    for (int j = M - 1; j >= 0; j--) {
        if (dp2[r][j].second && dp2[r][j].second >= l) {
            ans += dp2[r][j].first;
            r = dp2[r][j].second;
        }
    }
    return ans + 1ll * (r - l + 1) * a[r];
}

void doWork() {
    cin >> n;
    a[0] = a[n] = 2e9;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
    }

    preprocess();

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l > r) {
            swap(l, r);
            r--;
            int nxt = dp1[r][0].second;
            if (nxt == 0)nxt = n;
            r = nxt - 1;
            cout << solve1(l, r) << "\n";
        } else {
            int nxt = dp2[l][0].second;
            l = nxt + 1;
            cout << solve2(l, r - 1) << "\n";
        }
    }
}

int main() {
    IO
    preprocess();
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}