#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 7;
stack<int> st;
int n, m, a[maxn], ans[maxn];
vector<pair<int, int>> q[maxn];
vector<int> p[maxn];
struct Node
{
int l, r, ans;
Node(){};
Node(int l, int r, int ans): l(l), r(r), ans(ans) {};
Node operator + (const Node &other) const {
Node cc;
cc.l = max(l, other.l);
cc.r = max(r, other.r);
cc.ans = max({ans, other.ans, l + other.r});
return cc;
}
} IT[4 * maxn];
void Build(int id, int l, int r)
{
if(l == r)
{
IT[id].r = a[l];
return;
}
int mid = l + r >> 1;
Build(id * 2, l, mid);
Build(id * 2 + 1, mid + 1, r);
IT[id] = IT[id * 2] + IT[id * 2 + 1];
}
void Update(int id, int l, int r, int u, int val)
{
if(l == r)
{
IT[id].l = max(IT[id].l, val);
return;
}
int mid = l + r >> 1;
if(u <= mid) Update(id * 2, l, mid, u, val);
else Update(id * 2 + 1, mid + 1, r, u, val);
IT[id] = IT[id * 2] + IT[id * 2 + 1];
}
Node Query(int id, int l, int r, int u, int v)
{
if(l > v || r < u) return {0, 0, 0};
if(u <= l && r <= v)
{
return IT[id];
}
int mid = l + r >> 1;
return Query(id * 2, l, mid, u, v) + Query(id * 2 + 1, mid + 1, r, u, v);
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
cin >> n;
/// first we need to list all the potential pair for 2 elements (a, b)
/// if it exists k such that a < k < b and a[k] > a[b], (a, b) will not the optimal pair we need because we can choose (a, k) for a better solution
/// in the same way if it exists k such that a < k < b and a[a] < a[k] < a[b], (a, b) will not the optimal pair we need because we can choose (k, b) for a better solution
/// => for every k such that a < k < b, there must be a[a] > a[k] and a[k] < a[b]
for(int i = 1; i <= n; i++)
{
cin >> a[i];
while(!st.empty() && a[st.top()] <= a[i])
{
p[st.top()].push_back(i);
st.pop();
}
if(!st.empty()) p[st.top()].push_back(i);
st.push(i);
}
Build(1, 1, n);
cin >> m;
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
q[u].emplace_back(v, i);
}
for(int i = n; i >= 1; i--)
{
for(auto j: p[i])
{
int cc = 2 * j - i - 1;
if(cc <= n)
Update(1, 1, n, cc, a[i] + a[j]);
}
for(auto j: q[i])
{
ans[j.second] = Query(1, 1, n, i, j.first).ans;
}
}
for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
