#include <bits/stdc++.h>
#define isb ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ent "\n"
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
const ll INF = 9223372036854775807;
const int inf = INT_MAX;
int n, m;
ll a[maxn];
ll d[maxn*4];
vector<int> q[maxn];
vector<pair<int, int>> e[maxn];
int t[maxn*4];
int c[maxn*4];
int ans[maxn*4];
int res[maxn];
void build(int v, int tl, int tr){
if(tl == tr){
d[v] = a[tl];
} else{
int mid = (tl + tr) / 2;
build(v*2, tl, mid);
build(v*2+1, mid+1, tr);
d[v] = max(d[v*2], d[v*2+1]);
}
}
int getp(int v, int tl, int tr, int pos, int x){
if(tr <= pos) return 0;
if(d[v] < x) return 0;
if(tl == tr) return tl;
int mid = (tl + tr) / 2;
int num = getp(v*2, tl, mid, pos, x);
if(num != 0) return num;
return getp(v*2+1, mid+1, tr, pos, x);
}
int getb(int v, int tl, int tr, int pos, int x){
if(d[v] < x) return 0;
if(pos <= tl) return 0;
if(tl == tr) return tr;
int mid = (tl + tr) / 2;
int num = getb(v*2+1, mid+1, tr, pos, x);
if(num != 0) return num;
return getb(v*2, tl, mid, pos, x);
}
void push(int v){
if(t[v] == -1) return;
c[v*2] = t[v];
c[v*2+1] = t[v];
ans[v*2] = c[v*2] + d[v*2];
ans[v*2+1] = c[v*2+1] + d[v*2+1];
t[v*2] = t[v];
t[v*2+1] = t[v];
t[v] = -1;
}
int getf(int v, int tl, int tr, int l, int x){
if(tl != tr) push(v);
if(tr < l) return 0;
if(c[v] < x) return 0;
if(tl == tr) return tl;
int mid = (tl + tr) / 2;
int num = getf(v*2, tl, mid, l, x);
if(num != 0) return num;
return getf(v*2+1, mid+1, tr, l, x);
}
void upd(int v, int tl, int tr, int l, int r, int x){
if(tl != tr) push(v);
if(tl > r || tr < l) return;
if(l <= tl && tr <= r){
c[v] = t[v] = x;
ans[v] = d[v] + x;
} else{
int mid = (tl + tr) / 2;
upd(v*2, tl, mid, l, r, x);
upd(v*2+1, mid+1, tr, l, r, x);
ans[v] = max(ans[v*2], ans[v*2+1]);
c[v] = max(c[v*2], c[v*2+1]);
}
}
int get(int v, int tl, int tr, int l, int r){
if(tl != tr) push(v);
if(tl > r || tr < l) return 0;
if(l <= tl && tr <= r) return ans[v];
int mid = (tl + tr) / 2;
return max(get(v*2, tl, mid, l, r), get(v*2+1, mid+1, tr, l, r));
}
void asd(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
for(int i = 1; i <= n; i++){
int j = getp(1, 1, n, i, a[i]);
int k = getb(1, 1, n, i, a[i]);
if(i + 2 <= n && j*2-i <= n && j != 0){
q[i].push_back(j);
}
if(i > 1 && 2*i-k <= n && k != 0){
q[k].push_back(i);
}
}
cin >> m;
for(int i = 1; i <= m; i++){
int l, r;
cin >> l >> r;
e[l].push_back({r, i});
}
for(int i = n; i; i--){
for(int x: q[i]){
int tl = x*2-i;
int tr = getf(1, 1, n, tl, a[i] + a[x]);
if(c[1] < a[i] + a[x]) tr = n+1;
if(tr != 0) upd(1, 1, n, tl, tr-1, a[i] + a[x]);
}
for(auto x: e[i]){
res[x.second] = get(1, 1, n, i, x.first);
}
}
for(int i = 1; i <= m; i++){
cout << res[i] << ent;
}
}
int main(){
isb;
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++) asd(), cout << ent;
}
