#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
const int N = 5e5+1;
int n, q, ans[N];
vector<pii> queries[N], vec[N];
struct Segtree {
vector<int> node, push, max_in_range;
int base;
void init(int sz, vector<int> leaves) {
base = 1;
while(base < sz) base *= 2;
node.resize(2*base+1);
push.resize(2*base+1);
max_in_range.resize(2*base+1);
for(int i=0; i<(int)leaves.size(); ++i) {
max_in_range[i+base] = leaves[i];
}
for(int i=base-1; i>=1; --i) {
max_in_range[i] = max(max_in_range[i*2], max_in_range[i*2+1]);
}
}
void Push(int x, int y) {
node[y] = max(node[y], push[x] + max_in_range[y]);
push[y] = max(push[y], push[x]);
}
void ins(int l, int r, int val, int id, int L, int R) {
if(l > R || r < L) return;
if(L>=l && R<=r) {
node[id] = max(node[id], val + max_in_range[id]);
push[id] = max(push[id], val);
return;
}
int M = (L+R)/2;
Push(id, id*2); Push(id, id*2+1);
ins(l, r, val, id*2, L, M);
ins(l, r, val, id*2+1, M+1, R);
node[id] = max(node[id*2], node[id*2+1]);
}
int qry(int l, int r, int id, int L, int R) {
if(l > R || r < L) return 0;
if(L>=l && R<=r) {
return node[id];
}
int M = (L+R)/2;
Push(id, id*2); Push(id, id*2+1);
int res = max(qry(l, r, id*2, L, M), qry(l, r, id*2+1, M+1, R));
node[id] = max(node[id*2], node[id*2+1]);
return res;
}
};
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
vector<int> a(n);
for(int i=0; i<n; ++i) {
cin>>a[i];
}
Segtree tree;
tree.init(n, a);
cin>>q;
for(int i=0; i<q; ++i) {
int l, r; cin>>l>>r;
queries[l-1].push_back(mp(r-1, i));
}
vector<int> mono;
for(int i=0; i<n; ++i) {
while(mono.size() && a[mono.back()] <= a[i]) {
vec[mono.back()].push_back(mp(a[i] + a[mono.back()], i+(i-mono.back())));
mono.pop_back();
}
if(mono.size()) {
vec[mono.back()].push_back(mp(a[i] + a[mono.back()], i+(i-mono.back())));
}
mono.push_back(i);
}
for(int i=n-1; i>=0; --i) {
for(auto j: vec[i]) {
if(j.nd > n-1) continue;
tree.ins(j.nd, n-1, j.st, 1, 0, tree.base-1);
}
for(auto j: queries[i]) {
ans[j.nd] = tree.qry(i, j.st, 1, 0, tree.base-1);
}
}
for(int i=0; i<q; ++i) {
cout<<ans[i]<<'\n';
}
}
