#include <bits/stdc++.h>
#define a first
#define b second
#define ab first
#define value second
#define r first
#define id second
#define int long long
using namespace std;
typedef pair<int,int> ii;
const int inf = 102345678901;
const int N = 1<<19;
int arr[N];
int ans[N];
vector<ii> updates[N];
vector<ii> queries[N];
struct node{ int c, ab, abc; };
node tree[2*N];
node relax(node L, node R){
return { max(L.c, R.c), max(L.ab, R.ab), max(L.ab+R.c, max(L.abc, R.abc)) };
}
void init(){
for(int i = N;i < 2*N;i++) tree[i] = {arr[i-N], -inf, -inf};
for(int i = N-1;i >= 1;i--) tree[i] = relax(tree[i<<1], tree[i<<1|1]);
}
void update(int i, int ab){
i += N;
tree[i].ab = max(tree[i].ab, ab);
tree[i].abc = max(tree[i].ab + tree[i].c, tree[i].abc);
for(i >>= 1;i > 0;i >>= 1) tree[i] = relax(tree[i<<1], tree[i<<1|1]);
}
int query(int l, int r){
node L = {-inf,-inf,-inf};
node R = {-inf,-inf,-inf};
for(l += N, r += N;l < r;l >>= 1, r >>= 1){
if(l&1) L = relax(L, tree[l++]);
if(r&1) R = relax(tree[--r], R);
}
return relax(L,R).abc;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i];
vector<ii> goodpairs;
stack<int> S;
for(int i = 0;i < n;i++){
while(!S.empty()){
int top = S.top();
goodpairs.push_back(ii(top,i));
if(arr[i] >= arr[top]) S.pop();
else break;
}
S.push(i);
}
for(ii p : goodpairs){
int ab = p.b * 2 - p.a;
if(ab < n) updates[p.a].push_back(ii(ab, arr[p.a] + arr[p.b]));
}
int Q; cin >> Q;
for(int q = 0;q < Q;q++){
int l, r; cin >> l >> r; l--; r--;
queries[l].push_back(ii(r,q));
}
init();
for(int l = n-1;l >= 0;l--){
for(ii u : updates[l]){
update(u.ab, u.value);
}
for(ii q : queries[l]){
int r = q.r;
ans[q.id] = query(l, r+1);
}
}
for(int q = 0;q < Q;q++) cout << ans[q] << "\n";
}
