#include<bits/stdc++.h>
using namespace std;
const int N = (int)5e5+7;
const int M = (int)2e5+7;
const int inf = (int)1e9+7;
int n, q, a[N], b[N], ans[N];
pair<int, int> suf[N];
int L[N], R[N];
vector<pair<int, int> > Q[N];
vector<int> adj[N];
void upd(int l, int r, int x) {
for(int i = l; i <= r; ++i) {
b[i] = max(b[i], x);
}
}
int get(int l, int r) {
int res=0;
for(int i = l; i <= r; ++i) {
res = max(res, a[i]+b[i]);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
cin >> q;
stack<int> st;
for(int i = 1; i <= n; ++i) {
L[i] = i;
while(!st.empty() && a[st.top()]<a[i]) {
L[i]=L[st.top()];
st.pop();
}
st.push(i);
}
while(!st.empty()) {
continue;
}
for(int i = n; i >= 1; --i) {
R[i] = i;
while(!st.empty() && a[st.top()]<a[i]) {
R[i] = R[st.top()];
st.pop();
}
st.push(i);
}
for(int i = 1; i <= n; ++i) {
if(R[i]+1<=n) {
adj[i].push_back(R[i]+1);
}
if(L[i]-1>=1) {
adj[L[i]-1].push_back(i);
}
}
for(int i = 1; i <= q; ++i) {
int l, r;
cin >> l >> r;
Q[l].push_back({r, i});
}
for(int l = n; l >= 1; --l) {
{
for(int j : adj[l]) {
int i = l;
upd(2*j-i, n, a[i]+a[j]);
}
}
for(auto [r, i] : Q[l]) {
ans[i] = max(ans[i], get(l, r));
}
}
for(int i = 1; i <= q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
