#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 2e5 + 5;
int n, q, a[N];
int prv[N], nxt[N];
ll ans[N], ansR[N];
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i < n;i++)
		cin >> a[i];
    stack<int> st;
    for(int i = 1;i < n;i++) {
		while(!st.empty() && a[st.top()] < a[i])
			st.pop();
		if(st.empty())
			prv[i] = 0;
		else
			prv[i] = st.top();
		st.push(i);
	}
	st = {};
	for(int i = n - 1;i >= 1;i--) {
		while(!st.empty() && a[st.top()] < a[i])
			st.pop();
		if(st.empty())
			nxt[i] = n;
		else
			nxt[i] = st.top();
		st.push(i);
	}
	for(int i = 1;i < n;i++)
		ans[i] = ans[prv[i]] + (i - prv[i]) * 1ll * a[i];
	for(int i = n - 1;i >= 1;i--)
		ansR[i] = ansR[nxt[i]] + (nxt[i] - i) * 1ll * a[i];
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		if(l <= r)
			cout << ans[r - 1] - ans[prv[l]] << '\n';
		else
			cout << ansR[r] - ansR[nxt[l] - 1] << '\n';
	}
    return 0;
}