#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5;
int st[4 * maxn], val[4 * maxn], lazy[4 * maxn], a[maxn];
void build(int id, int l, int r){
if(l == r) val[id] = a[l];
else{
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
val[id] = max(val[id * 2], val[id * 2 + 1]);
}
}
void down(int id){
lazy[id * 2] = max(lazy[id * 2], lazy[id]);
lazy[id * 2 + 1] = max(lazy[id * 2 + 1], lazy[id]);
st[id * 2] = max(st[id * 2], lazy[id] + val[id * 2]);
st[id * 2 + 1] = max(st[id * 2 + 1], lazy[id] + val[id * 2 + 1]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u) return;
if(u <= l && r <= v){
lazy[id] = max(lazy[id], x);
st[id] = max(st[id], val[id] + x);
return;
}
down(id);
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, x);
update(id * 2 + 1, mid + 1, r, u, v, x);
st[id] = max(st[id * 2], st[id * 2 + 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];
down(id);
int mid = (l + r) / 2;
return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
void solve(){
int n; cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int q; cin >> q;
if(n <= 1 && q <= 100){
while(q--){
int l, r; cin >> l >> r;
int ans = 0;
for(int i = l; i <= r; i++){
for(int j = i + 1; j <= r; j++){
for(int k = j + 1; k <= r; k++){
if(k - j >= j - i){
ans = max(ans, a[i] + a[j] + a[k]);
}
}
}
}
cout << ans << "\n";
}
}else if(n <= 1){
vector<vector<int>> mx(n + 1, vector<int>(n + 1)), dp(n + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++){
mx[i][i] = a[i];
for(int j = i + 1; j <= n; j++) mx[i][j] = max(mx[i][j - 1], a[j]);
}
for(int len = 2; len <= n - 1; len++){
for(int i = 1; i + len <= n; i++){
int j = i + len;
int mid = (i + j) / 2;
int L = max(1ll, i + 1), R = min(mid, j - 1);
dp[i][j] = a[i] + mx[L][R] + a[j];
dp[i][j] = max({dp[i][j], dp[i + 1][j], dp[i][j - 1]});
}
}
while(q--){
int l, r; cin >> l >> r;
cout << dp[l][r] << "\n";
}
}else{
//nhận xét với cặp i, j. thì max[i + 1, j - 1] < min(a[i], a[j]); tìm k trên suffix max
//đẩy lên segment tree
stack<int> s;
vector<vector<pair<int, int>>> qry(n + 1);
vector<vector<int>> at(n + 1);
vector<int> ans(q + 1);
for(int i = 1; i <= n; i++){
while(!s.empty() && a[s.top()] <= a[i]){
at[s.top()].push_back(i);
s.pop();
}
if(!s.empty()) at[s.top()].push_back(i);
s.push(i);
}
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
qry[l].push_back({r, i});
}
build(1, 1, n);
for(int i = n; i >= 1; i--){
for(auto j: at[i]) if(2 * j - i <= n) update(1, 1, n, 2 * j - i, n, a[i] + a[j]);
for(auto [r, id]: qry[i]) ans[id] = get(1, 1, n, i, r);
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
