#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long
ll const INF = 1e9;
vector<int> vect;
struct node{
int s, e, m;
ll aval, summ, pv, lazy;
node *l, *r;
node (int S, int E)
{
s = S, e = E, m = (s+e)/2;
summ = pv = -INF;
if (s==e) {aval = vect[s]; return;}
l = new node(s, m);
r = new node(m+1, e);
aval = max(l->aval, r->aval);
lazy = -INF;
}
void propogate()
{
if (lazy==-INF) return;
if (s!=e)
{
l->lazy = max(l->lazy, lazy);
r->lazy = max(r->lazy, lazy);
l->pv= max(l->pv, lazy);
l->summ = max(l->summ, l->aval + lazy);
r->pv= max(r->pv, lazy);
r->summ = max(r->summ, r->aval + lazy);
}
lazy = -INF;
}
void update(int S, int E, ll V)
{
if (S>E)return;
propogate();
if(s==S && e==E)
{
lazy = max(lazy, V);
pv= max(pv, V);
summ = max(summ, aval + pv);
}
else{
propogate();
if(E <= m) l->update(S, E, V);
else if (m < S) r->update(S, E, V);
else l->update(S, m, V),r->update(m+1, E, V);
l->propogate(),r->propogate();
summ = max(l->summ, r->summ);
}
}
ll query(int S, int E)
{
propogate();
if(s == S && e == E) return summ;
propogate();
if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else return max(l->query(S, m), r->query(m+1, E));
}
} *st;
int32_t main(){
int n, q, a, b;
cin>>n;
vect.resize(n+1);
vector<vector<pii> > queries(n+1);
for (int i=1; i<=n; ++i)cin>>vect[i];
cin>>q;
vector<int> ans(q);
vector<vector<int> > next(n+1);
st = new node(1, n);
for (int i=0; i<q; ++i){
cin>>a>>b;
queries[a].pb(mp(b, i));
}
stack<int> s;
for (int i=1; i<=n; ++i){
while (!s.empty()&&vect[s.top()]<=vect[i])next[s.top()].pb(i), s.pop();
s.push(i);
}
while (!s.empty())s.pop();
for (int i=n; i>=1; --i){
while (!s.empty()&&vect[s.top()]<=vect[i])next[i].pb(s.top()), s.pop();
s.push(i);
}
for (int i=n; i>=1; --i){
for (auto c:next[i])st->update(2*c-i, n, vect[i]+vect[c]);
for (auto c:queries[i])ans[c.se]=st->query(i, c.fi);
}
for (auto a:ans)cout<<a<<"\n";
}
