#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
const int N = 5e5 + 10;
const int inf = 1e15;
const int mod = 1e9 + 7;
vector<pair<int,int>>kveri[N],upd[N];
int ans[N],lazy[N * 4],a[N];
struct cvor {
int mx,ans,lazy;
};
cvor st[N * 4];
void build(int node,int tl,int tr) {
if(tl == tr) {
st[node].ans = a[tl];
st[node].mx = a[tl];
st[node].lazy = 0;
return;
}
int mid = (tl + tr) / 2;
build(node * 2,tl,mid);
build(node * 2 + 1,mid + 1,tr);
st[node].ans = max(st[node * 2].ans,st[node * 2 + 1].ans);
st[node].mx = max(st[node * 2].mx,st[node * 2 + 1].mx);
}
void push(int node,int tl,int tr) {
st[node].ans = max(st[node].ans,st[node].lazy + st[node].mx);
if(tl != tr) {
st[node * 2].lazy = max(st[node * 2].lazy,st[node].lazy);
st[node * 2 + 1].lazy = max(st[node * 2 + 1].lazy,st[node].lazy);
}
st[node].lazy = 0;
}
void modify(int node,int tl,int tr,int l,int r,int v) {
push(node,tl,tr);
if(tl > r || tr < l) return;
if(tl >= l && tr <= r) {
st[node].lazy = v;
push(node,tl,tr);
return;
}
int mid = (tl + tr) / 2;
modify(node * 2,tl,mid,l,r,v);
modify(node * 2 + 1,mid + 1,tr,l,r,v);
st[node].ans = max(st[node * 2].ans,st[node * 2 + 1].ans);
st[node].mx = max(st[node * 2].mx,st[node * 2 + 1].mx);
}
int get(int node,int tl,int tr,int l,int r) {
push(node,tl,tr);
if(tl > r || tr < l) return 0;
if(tl >= l && tr <= r) return st[node].ans;
int mid = (tl + tr) / 2;
return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin >> n;
vector<int> l(n + 1),r(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
build(1,1,n);
stack<int>st;
for(int i = 1; i <= n; i++) {
while(!st.empty() && a[st.top()] <= a[i]) st.pop();
l[i] = (st.empty() ? -1 : st.top());
st.push(i);
}
while(!st.empty()) st.pop();
for(int i = n; i >= 1; i--) {
while(!st.empty() && a[st.top()] <= a[i]) st.pop();
r[i] = (st.empty() ? n + 1 : st.top());
st.push(i);
}
cin >> q;
for(int i = 1; i <= q; i++) {
int ll,rr;
cin >> ll >> rr;
kveri[ll].pb({rr,i});
}
for(int i = 1; i <= n; i++) {
if(l[i] != -1) upd[l[i]].pb({2 * i - l[i],a[i] + a[l[i]]});
if(r[i] != n + 1) upd[i].pb({2 * r[i] - i,a[i] + a[r[i]]});
}
for(int i = n; i >= 1; i--) {
for(auto X : upd[i]) modify(1,1,n,X.F,n,X.S);
for(auto X : kveri[i]) {
ans[X.S] = get(1,1,n,i,X.F);
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
return 0;
}
