#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n; cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
int q; cin >> q;
if(n <= 100 && 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 <= 5000){
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{
vector<pair<int, int>> cand;
vector<int> suf(n + 1);
for(int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], a[i]);
//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
stack<int> st;
for(int i = 1; i <= n; i++){
while(!st.empty() && a[st.top()] <= a[i]){
cand.push_back({st.top(), i});
st.pop();
}
if(!st.empty()) cand.push_back({st.top(), i});
st.push(i);
}
int ans = 0;
for(auto [x, y]: cand) if(2 * y - x <= n) ans = max(ans, a[x] + a[y] + suf[2 * y - x]);
cout << ans;
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
}
