#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define pii pair<int,int>
#define el '\n'
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define N 5000006
using namespace std;
int st[N << 2], lazy[N << 2];
int A[N];
int ans[N];
int dp[21][N];
const int lg = 20;
vector<pii> vec[N];
int getmx(int l, int r){
int k = __lg(r - l + 1);
return max(dp[k][l], dp[k][r - (1 << k) + 1]);
}
void push(int id, int l, int r){
if (lazy[id] == 0) return;
int m = (l + r)/2;
st[id << 1] = max(st[id << 1], lazy[id] + getmx(l, m));
st[id << 1 | 1] = max(st[id << 1 | 1], lazy[id] + getmx(m + 1, r));
lazy[id << 1] = max(lazy[id << 1], lazy[id]);
lazy[id << 1 | 1] = max(lazy[id << 1 | 1], lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
if (l > v || r < u) return;
if (u <= l && r <= v){
st[id] = max(st[id], val + getmx(l, r));
lazy[id] = max(lazy[id], val);
return;
}
push(id, l, r);
int m = (l + r)/2;
update(id << 1, l, m, u, v, val);
update(id << 1 | 1, m + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
if (l > v || r < u) return 0;
if (u <= l && r <= v) return st[id];
push(id, l, r);
int m = (l + r)/2;
return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, Q;
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i], dp[0][i] = A[i];
for (int j = 1; j <= lg; j++){
for (int i = 1; i <= n - (1 << j) + 1; i++){
dp[j][i] = max(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
}
}
cin >> Q;
for (int i = 1; i <= Q; i++){
int l, r;
cin >> l >> r;
vec[l].push_back({r, i});
}
stack<int> stk;
for (int i = n; i >= 1; i--){
while(!stk.empty() && A[i] >= A[stk.top()]){
update(1, 1, n, 2 * stk.top() - i, n, A[i] + A[stk.top()]);
stk.pop();
}
if (!stk.empty()){
update(1, 1, n, 2 * stk.top() - i, n, A[i] + A[stk.top()]);
}
stk.push(i);
for (auto [r, id] : vec[i]){
ans[id] = get(1, 1, n, i, r);
}
}
for (int i = 1; i <= Q; i++){
cout << ans[i] <<'\n';
}
}
