//khodaya khodet komak kon
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 500000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;
struct node{
int mx, num, ans;
};
struct query{
int id, R;
};
int n, m, a[N], lazy[N << 2], ans[N];
node seg[N << 2];
vector<query> L[N];
node merge(node x, node y){
node res = x;
res.mx = max(res.mx, y.mx);
res.num = max(res.num, y.num);
res.ans = max(res.ans, y.ans);
return res;
}
void modify(int id, int x){
seg[id].mx = x;
seg[id].ans = seg[id].mx + seg[id].num;
lazy[id] = x;
}
void shift(int id){
if (lazy[id] == -1) return;
modify(id << 1, lazy[id]);
modify(id << 1 | 1, lazy[id]);
lazy[id] = -1;
}
void build(int id, int l, int r){
if (r - l == 1){
seg[id].mx = seg[id].ans = 0;
seg[id].num = a[l];
return;
}
int md = (l + r) >> 1;
build(id << 1, l, md);
build(id << 1 | 1, md, r);
seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}
int BS(int id, int x, int l, int r){
if (r - l == 1){
// cout << "Fuck " << l << ' ' << r << ' ' << seg[id].mx << '\n';
if (seg[id].mx < x) return n + 1;
return l;
}
shift(id);
int md = (l + r) >> 1;
if (seg[id << 1].mx >= x) return BS(id << 1, x, l, md);
return BS(id << 1 | 1, x, md, r);
}
void Set(int id, int lq, int rq, int x, int l, int r){
if (rq <= lq) return;
if (rq <= l || r <= lq) return;
if (lq <= l && r <= rq){
modify(id, x);
// cout << "Fuck " << l << ' ' << r << ' ' << seg[id].mx << '\n';
return;
}
int md = (l + r) >> 1;
shift(id);
Set(id << 1, lq, rq, x, l, md);
Set(id << 1 | 1, lq, rq, x, md, r);
seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}
int get(int id, int lq, int rq, int l, int r){
if (rq <= l || r <= lq) return 0;
if (lq <= l && r <= rq){
return seg[id].ans;
}
shift(id);
int md = (l + r) >> 1;
return max(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++){
int l, r;
cin >> l >> r;
query res;
res.id = i, res.R = r;
L[l].pb(res);
}
build(1, 1, n + 1);
// cout << "YES" << endl;
stack<int> st;
st.push(n);
for (int i = n - 1; i >= 1; i--){
// cout << i << endl;
while (st.size() && a[st.top()] <= a[i]){
int sm = a[i] + a[st.top()];
int l = i, r = st.top();
int R = 2 * r - l;
if (R <= n){
// cout << "YES" << endl;
int koj = BS(1, sm, 1, n + 1);
// cout << l << ' ' << r << ' ' << sm << ' ' << koj << '\n';
Set(1, R, koj, sm, 1, n + 1);
// cout << "YES2" << endl;
}
st.pop();
}
// cout << "YES2" << endl;
if (st.size()){
int sm = a[i] + a[st.top()];
int l = i, r = st.top();
int R = 2 * r - l;
if (R <= n){
int koj = BS(1, sm, 1, n + 1);
// cout << l << ' ' << r << ' ' << sm << ' ' << koj << '\n';
Set(1, R, koj, sm, 1, n + 1);
}
}
st.push(i);
for (auto u:L[i]) ans[u.id] = get(1, i, u.R + 1, 1, n + 1);
}
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
return 0;
}
