#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
vector<int> vect;
struct node {
node *left, *right;
int S, E, val, r_val, A_val, pv;
node(int _s, int _e) : S(_s), E(_e), r_val(-(int)1e9), pv(-(int)1e9) {
if (S == E) {
A_val = vect[S];
return;
}
int M = (S + E) / 2;
left = new node(S, M);
right = new node(M + 1, E);
A_val = max(left->A_val, right->A_val);
}
void prop() {
left->r_val = max(left->r_val, pv + left->A_val);
left->pv = max(left->pv, pv);
right->r_val = max(right->r_val, pv + right->A_val);
right->pv = max(right->pv, pv);
}
void up(int l, int r, int v) {
if (l > E || r < S) {
return;
}
if (l <= S && E <= r) {
r_val = max(r_val, v + A_val);
pv = max(pv, v);
return;
}
prop();
left->up(l, r, v);
right->up(l, r, v);
r_val = max(left->r_val, right->r_val);
}
int query(int l, int r) {
if (l > E || r < S) {
return -(int)1e9;
}
if (l <= S && E <= r) {
return r_val;
}
prop();
return max(left->query(l, r), right->query(l, r));
}
} *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->up(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";
}
