/* I can do this all day */
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937 rng(time(nullptr));
int n, q, A[N];
vector < int > vec[N];
vector < pii > Q[N];
ll Ans[N], Mn[N << 2], Mx[N << 2], seg[N << 2], lz[N << 2];
void build(int v = 1, int tl = 1, int tr = n)
{
if(tl == tr)
{
seg[v] = A[tl];
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);
seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}
void Push(int v, ll x)
{
Mn[v] += x;
Mx[v] += x;
lz[v] += x;
seg[v] += x;
}
void S(int v, int tl, int tr)
{
if(tl == tr) return;
Push(v << 1, lz[v]);
Push(v << 1 | 1, lz[v]);
lz[v] = 0;
}
void upd(int l, int r, ll x, int v = 1, int tl = 1, int tr = n)
{
S(v, tl, tr);
if(l > tr || r < tl || l > r || Mn[v] >= x) return;
if(l <= tl && tr <= r && Mn[v] == Mx[v])
{
Push(v, x - Mn[v]);
return;
}
int mid = (tl + tr) >> 1;
upd(l, r, x, v << 1, tl, mid), upd(l, r, x, v << 1 | 1, mid + 1, tr);
seg[v] = max({seg[v << 1], seg[v << 1 | 1]});
Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]);
Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]);
}
ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
S(v, tl, tr);
if(l > tr || r < tl || l > r) return -inf;
if(l <= tl && tr <= r) return seg[v];
int mid = (tl + tr) >> 1;
return max(get(l, r, v << 1, tl, mid), get(l, r, v << 1 | 1, mid + 1, tr));
}
int main()
{
fast_io;
vector < int > S;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> A[i];
while(SZ(S) && A[S.back()] < A[i])
{
vec[S.back()].push_back(i);
S.pop_back();
}
if(SZ(S))
{
vec[S.back()].push_back(i);
}
S.push_back(i);
}
cin >> q;
for(int i = 1; i <= q; i ++)
{
int fir, sec;
cin >> fir >> sec;
Q[fir].push_back({sec, i});
}
build();
for(int i = n; ~(i - 1); i --)
{
for(auto id : vec[i])
{
///printf("i = %d id = %d\n", i, id);
upd(id * 2 - i, n, A[i] + A[id]);
}
for(auto cu : Q[i])
{
int id = cu.S, r = cu.F;
Ans[id] = get(i + 2, r);
}
/*printf("i = %d\n", i);
for(int j = 1; j <= n; j ++)
{
for(int k = j; k <= n; k ++)
{
printf("j = %d k = %d get = %lld\n", j, k, get(j, k));
}
}
printf("\n");
*/
}
for(int i = 1; i <= q; i ++)
{
cout << Ans[i] << endl;
}
return 0;
}
/* check corner case(n = 1?), watch for negetive index or overflow */
