#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define vv vector
/*void read(int &a){
char c = getchar_unlocked(); a = 0;
while(c<'0' || '9'<c) c = getchar_unlocked();
while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked();
}*/
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int base = 1;
struct seg{
struct Node{
int val, p, a;
Node(){ val = 0, p = 0, a = 0; }
};
vv<Node> t;
void init(int n, vv<int> &tt){
while(base < n) base <<= 1;
t.resize(base<<1);
for(int i = 1; i <= n; ++i) t[i+base-1].a = tt[i];
for(int i = base-1; i; --i) t[i].a = max(t[i<<1].a, t[i<<1|1].a);
}
void add(int i, int val){ t[i].val = max(t[i].val, t[i].a+val), t[i].p = max(t[i].p, val); }
void push(int i){ if(t[i].p) add(i<<1, t[i].p), add(i<<1|1, t[i].p), t[i].p = 0; }
void update(int i, int s, int e, int x, int y, int val){
if(x <= s && e <= y) return void(add(i, val));
int mid = (s+e)>>1; push(i);
if(x <= mid) update(i<<1, s, mid, x, y, val);
if(mid < y) update(i<<1|1, mid+1, e, x, y, val);
t[i].val = max(t[i<<1].val, t[i<<1|1].val);
}
int query(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i].val;
int mid = (s+e)>>1, result = 0; push(i);
if(x <= mid) result = max(result, query(i<<1, s, mid, x, y));
if(mid < y) result = max(result, query(i<<1|1, mid+1, e, x, y));
t[i].val = max(t[i<<1].val, t[i<<1|1].val);
return result;
}
};
void answer(){
int n; scanf("%d", &n);
vv<int> t(n+1);
for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
vv<vv<int>> v(n+1); //valid
vv<int> st; st.emplace_back(n-1);
for(int i = n-2; i; --i){
while(ssize(st) && t[st.back()] <= t[i]) v[i].emplace_back(st.back()), st.pop_back();
if(ssize(st)) v[i].emplace_back(st.back());
st.emplace_back(i);
}
int q; scanf("%d", &q);
vv<vv<pii>> qr(n+1);
vv<int> result(q);
for(int i = 0, a, b; i < q; ++i) scanf("%d%d", &a, &b), qr[a].emplace_back(b, i);
seg seg; seg.init(n, t);
for(int i = n-2; i; --i){
for(int &j : v[i]) if(2*j-i <= n) seg.update(1, 1, base, 2*j-i, n, t[i]+t[j]);//, printf("%d %d\n", i, j);
for(pii &u : qr[i]) result[u.se] = seg.query(1, 1, base, i, u.fi);
}
for(int i = 0; i < q; ++i) printf("%d\n", result[i]);
}
signed main(){
int T = 1;
//~ scanf("%d", &T);
//~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T;
for(++T; --T; ) answer();
return 0;
}
