#include <bits/stdc++.h>
using namespace std;
const int Nmax = 5e5 + 5;
const int inf = 1e9;
vector<int> start[Nmax], query[Nmax];
vector<pair<int,int>> v;
int a[Nmax], st[Nmax];
int n, L[Nmax], R[Nmax];
int ans[Nmax];
#define left_son ((node<<1))
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
class SegTree
{
int best[Nmax<<2];
int mx[Nmax<<2];
int lazy[Nmax<<2];
void propag(int node)
{
if(!lazy[node]) return;
best[left_son] = max(best[left_son], mx[left_son] + lazy[node]);
best[right_son] = max(best[right_son], mx[right_son] + lazy[node]);
lazy[left_son] = max(lazy[left_son], lazy[node]);
lazy[right_son] = max(lazy[right_son], lazy[node]);
lazy[node] = 0;
}
public:
void init(int node, int st, int dr)
{
lazy[node] = 0;
best[node] = -inf;
if(st == dr)
{
mx[node] = a[st];
return;
}
init(left_son, st, mid);
init(right_son, mid+1, dr);
mx[node] = max(mx[left_son], mx[right_son]);
}
void update(int node, int st, int dr, int L, int R, int coef)
{
if(L <= st && dr <= R)
{
lazy[node] = max(lazy[node], coef);
best[node] = max(best[node], mx[node] + coef);
return;
}
propag(node);
if(L <= mid) update(left_son, st, mid, L, R, coef);
if(mid < R) update(right_son, mid+1, dr, L, R, coef);
best[node] = max(best[left_son], best[right_son]);
}
int query(int node, int st, int dr, int L, int R)
{
if(L <= st && dr <= R)
return best[node];
propag(node);
int ans = -inf;
if(L <= mid) ans = max(ans, query(left_son, st, mid, L, R));
if(mid < R) ans = max(ans, query(right_son, mid+1, dr, L, R));
return ans;
}
} aint;
void fnd()
{
int i, nr = 0;
st[0] = 0;
a[0] = inf;
for(i=1; i<=n; ++i)
{
while(a[st[nr]] <= a[i])
{
v.push_back({st[nr], i});
--nr;
}
v.push_back({st[nr], i});
st[++nr] = i;
}
}
int main()
{
// freopen("triple.in", "r", stdin);
cin.tie(0); cin.sync_with_stdio(false);
cin >> n;
int i, q;
for(i=1; i<=n; ++i) cin >> a[i];
fnd();
cin >> q;
for(i=1; i<=q; ++i) cin >> L[i] >> R[i];
for(auto it : v)
start[it.first].push_back(it.second);
for(i=1; i<=q; ++i)
query[L[i]].push_back(i);
aint.init(1, 1, n);
for(i=n; i; --i)
{
for(auto it : start[i])
{
int R = 2 * it - i;
if(R <= n)
aint.update(1, 1, n, R, n, a[i] + a[it]);
}
for(auto it : query[i])
ans[it] = aint.query(1, 1, n, i, R[it]);
}
for(i=1; i<=q; ++i) cout << ans[i] << '\n';
return 0;
}
