#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define print(x) cout << #x <<" = " << x << endl
#define pprint(x) cout << #x <<" = (" << x.first <<" , " << x.second <<")\n"
#define ceil(a, b) ((a + b - 1) / b)
#define all(x) x.begin(), x.end()
#define INF 1000000000000000000
#define MAXN 1000005
#define MOD 1000000007
#define eps (1e-9)
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define get(L, R) ((L + R) | (L != R))
using namespace std;
struct node {
int A , B, C;
};
struct query {
int L, R, id;
bool operator<(query b) {
return L > b.L;
}
};
int n, q;
vector<query> qry;
vector<int> a, ans;
vector<vector<int>> ps;
vector<node> seg;
void build() {
stack<int> st;
rep(i, 1, n) {
while(st.size() && a[st.top()] <= a[i]) {
ps[st.top()].push_back(i), st.pop();
}
if(st.size()) ps[st.top()].push_back(i);
st.push(i);
}
// rep(i, 1, n) {
// print(i), puts("");
// for(auto j : ps[i]) print(j);
// puts("\n\n");
// }
return;
}
void pull(int L, int R) {
int mid = (L + R) / 2, nd = get(L, R);
seg[nd].A = max(seg[get(L, mid)].A, seg[get(mid + 1,R)].A);
seg[nd].C = max({seg[get(L, mid)].C, seg[get(mid + 1,R)].C, seg[nd].A + seg[nd].B });
return;
}
void build1(int L, int R) {
if(L == R) seg[get(L, R)].A = seg[get(L,R)].C = a[L] ;
else {
int mid = (L + R) / 2;
build1(L, mid), build1(mid + 1, R);
pull(L, R);
}
return;
}
void modify(int L, int R, int l, int r, int val) {
// pprint(pii(L,R)), print(val);
if(l > R || r < L) return;
if(l <= L && r >= R) {
// print(val);
seg[get(L, R)].B = max(seg[get(L, R)].B, val);
seg[get(L, R)].C = max(seg[get(L,R)].C, seg[get(L, R)].B + seg[get(L,R)].A);
// print(seg[get(L,R)].C);
}
else {
int mid = (L + R) / 2;
modify(L, mid, l, r, val), modify(mid + 1, R, l, r, val);
pull(L,R);
}
return;
}
pii query(int L, int R, int l, int r) {
if(l > R || r < L) return {0, 0};
// pprint(pii(L,R));
if(l <= L && r >= R) {
// pprint(pii(seg[get(L,R)].A, seg[get(L,R)].C));
return pii(seg[get(L,R)].A, seg[get(L,R)].C);
}
else {
int mid = (L + R) / 2;
pii a = query(L, mid, l, r), b = query(mid + 1, R, l, r);
int ans = max(max(a.first, b.first) + seg[get(L,R)].B, max(a.second, b.second));
pii rr = pii(max(a.first, b.first), ans);
// pprint(pii(L,R)), pprint(rr);
return rr;
}
}
void proc(int id) {
for(int i : ps[id]) {
int rr = 2 * i - id;
if(rr > n) continue;
modify(1, n, rr, n, a[i] + a[id]);
}
return;
}
void solve() {
build(), build1(1, n), sort(all(qry));
int cur = n;
for(auto i : qry) {
while(cur >= i.L) proc(cur--);
// pprint(pii(i.L, i.R));
pii aa = query(1, n, i.L + 2, i.R);
ans[i.id] = aa.second;
// puts("\n\n");
}
return;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n, seg.resize(2 * n + 2);
a.assign(n + 1 ,0), ps.assign(n + 1, vector<int>(0));
rep(i, 1, n) cin >> a[i];
cin >> q, qry.resize(q), ans.resize(q);
rep(i, 0, q-1) cin >> qry[i].L >> qry[i].R, qry[i].id = i;
solve();
rep(i, 0, q-1) cout << ans[i] <<"\n";
return 0;
}
