#include <bits/stdc++.h>
using namespace std;
const int nu = 5e5+5;
int n, query, a[nu], x[nu], y[nu];
int lon[nu], ans[nu];
vector<int> q[nu], be[nu];
stack<int> st1, st2;
int lazy[nu*4], it[nu*4], ma[nu*4];
void build(int id, int l, int r)
{
if(l == r) ma[id] = a[l];
else
{
int mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
ma[id] = max(ma[id*2], ma[id*2+1]);
}
}
void update(int id, int l, int r, int u, int v, int val)
{
if(v < l || u > r) return ;
else if(u <= l && r <= v)
{
it[id] = max(it[id], val+ma[id]);
lazy[id] = max(lazy[id], val);
}
else
{
int mid = (l+r)/2;
it[id*2] = max(it[id*2], lazy[id]+ma[id*2]); lazy[id*2] = max(lazy[id*2], lazy[id]);
it[id*2+1] = max(it[id*2+1], lazy[id]+ma[id*2+1]); lazy[id*2+1] = max(lazy[id*2+1], lazy[id]);
lazy[id] = -1e9;
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
it[id] = max(it[id*2], it[id*2+1]);
}
}
int getmax(int id, int l, int r, int u, int v)
{
if(v < l || u > r) return -1e9;
else if(u <= l && r <= v) return it[id];
else
{
int mid = (l+r)/2;
it[id*2] = max(it[id*2], lazy[id]+ma[id*2]); lazy[id*2] = max(lazy[id*2], lazy[id]);
it[id*2+1] = max(it[id*2+1], lazy[id]+ma[id*2+1]); lazy[id*2+1] = max(lazy[id*2+1], lazy[id]);
lazy[id] = -1e9;
return max(getmax(id*2, l, mid, u, v), getmax(id*2+1, mid+1, r, u, v));
}
}
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];
cin >> query;
for(int i = 1; i <= query; ++i)
{
cin >> x[i] >> y[i];
q[x[i]].push_back(i);
}
st1.push(n+1); st2.push(0);
for(int i = n; i > 0; --i)
{
while(int(st1.size()) > 1 && a[st1.top()] < a[i]) st1.pop();
//while(int(st2.size()) > 1 && a[st2.top()] > a[i]) st2.pop();
//be[i] = st2.top();
lon[i] = st1.top();
//st2.push(i);
st1.push(i);
}
for(int i = 1; i <= n; ++i)
{
while(int(st2.size()) > 1 && a[st2.top()] < a[i]) st2.pop();
be[st2.top()].push_back(i);
st2.push(i);
}
build(1, 1, n);
for(int i = 1; i <= 4*n; ++i) it[i] = lazy[i] = -1e9;
for(int i = n; i > 0; --i)
{
int aa = i; int b;
int c = 2*b-aa;
for(int j = 0; j < int(be[i].size()); ++j)
{
int qq = be[i][j];
if(qq <= n && 2*qq-i <= n) update(1, 1, n, 2*qq-i, n, a[i]+a[qq]);
}
// if(be[i] <= n && c <= n) update(1, 1, n, c, n, a[i]+a[be[i]]), cout << c << ' ' << n << ' ' << a[i]+a[be[i]] << ' ' << i << '\n';
b = lon[i]; c = 2*b-aa;
if(lon[i] <= n && c <= n) update(1, 1, n, c, n, a[i]+a[lon[i]]);
for(int j = 0; j < int(q[i].size()); ++j)
{
int p = q[i][j];
ans[p] = getmax(1, 1, n, x[p], y[p]);
}
}
for(int i = 1; i <= query; ++i) cout << ans[i] << '\n';
return 0;
}
