//#pragma GCC optimize("O2")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, q;
int a[N];
int Lq[N], Rq[N];
namespace sub1{
int ma[N];
void solve(){
for(int _ = 1; _ <= q; _++) {
// int L, R; cin >> L >> R;
int L = Lq[_], R = Rq[_];
long long ans = 0;
for(int i = L; i <= R; i++){
for(int j = L; j <= i - 1; j++){
ma[i - j] = a[j] + a[i];
}
for(int len = 0; len <= R - L + 1; len++){
ma[len] = max(ma[len], ma[len - 1]);
}
for(int j = i + 1; j <= R; j++){
ans = max(ans, a[j] + 1LL * ma[j - i]);
}
}
cout << ans << "\n";
for(int len = 0; len <= R - L + 1; len++){
ma[len] = - 2e9;
}
}
}
}
namespace sub2{
long long lazy[4 * N], st[4 * N], mx[4 * N];
void down(int id){
if(lazy[id] == 0) return;
st[id << 1] = max(st[id << 1], mx[id << 1] + lazy[id]);
st[id << 1 | 1] = max(st[id << 1 | 1], mx[id << 1 | 1] + lazy[id]);
lazy[id << 1] = max(lazy[id << 1], lazy[id]);
lazy[id << 1 | 1] = max(lazy[id << 1 | 1], lazy[id]);
lazy[id] = 0;
}
void build(int id, int l, int r){
if(l == r){
mx[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
}
void update(int id, int l, int r, int u, int v, long long val){
if(l > v || r < u) return;
if(l >= u && r <= v){
st[id] = max(st[id], mx[id] + val);
lazy[id] = max(lazy[id], val);
return;
}
down(id);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
long long get(int id, int l, int r, int u, int v){
if(l > v || r < u) return 0;
if(l >= u && r <= v) return st[id];
down(id);
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
long long ans[N];
vector <pair <int, int>> qry[N];
void solve(){
build(1, 1, n);
for(int i = 1; i <= q; i++){
qry[Lq[i]].push_back(make_pair(Rq[i], i));
}
stack <int> st;
for(int i = n; i >= 1; i--){
while(!st.empty() && a[i] >= a[st.top()]){
update(1, 1, n, max(1, 2 * st.top() - i), n, a[i] + a[st.top()]);
st.pop();
}
if(st.size()) update(1, 1, n, max(1, 2 * st.top() - i), n, a[i] + a[st.top()]);
st.push(i);
for(auto x : qry[i]){
ans[x.second] = max(ans[x.second], get(1, 1 , n, i, x.first));
}
}
for(int i = 1; i <= q; i++){
cout << ans[i] << "\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define KO ""
if(fopen(KO".inp", "r")){
freopen(KO".inp", "r", stdin); freopen(KO".out", "w", stdout);
}
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> q;
for(int i = 1; i <= q; i++){
cin >> Lq[i] >> Rq[i];
}
// return sub1 :: solve(), 0;
return sub2 :: solve(), 0;
return void(cerr << "\nKO : " << 0.001 * clock() << "s "), 0;
}
