//
// Created by adavy on 5/28/2025.
//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int ssz = 524288;
ll INF = 1e18;
int n;
vector<ll> nums;
vector<ll> nummax(ssz*2, -INF);
vector<ll> seg(ssz*2, -INF);
vector<ll> lz(ssz*2, -INF);
void pushdown(int rt, int tl, int tr){
seg[rt] = max(seg[rt], lz[rt] + nummax[rt]);
if (tl != tr) {
lz[2 * rt] = max(lz[2 * rt], lz[rt]);
lz[2 * rt + 1] = max(lz[2 * rt + 1], lz[rt]);
}
lz[rt] = -INF;
}
ll query(int l, int r, int rt, int tl, int tr){
pushdown(rt, tl, tr);
if (l > tr || r < tl) return -INF;
if (l <= tl && tr <= r) return seg[rt];
int tm = (tl + tr) / 2;
return max(query(l, r, 2 * rt, tl, tm), query(l, r, 2 * rt + 1, tm + 1, tr));
}
void update(ll x, int l, int r, int rt, int tl, int tr){
pushdown(rt, tl, tr);
if (l > tr || r < tl) return;
if (l <= tl && tr <= r) {
lz[rt] = max(lz[rt], x);
pushdown(rt, tl, tr);
return;
}
int tm = (tl + tr) / 2;
update(x, l, r, 2 * rt, tl, tm);
update(x, l, r, 2 * rt + 1, tm + 1, tr);
seg[rt] = max(seg[2 * rt], seg[2 * rt + 1]);
}
void set_nummax(){
for(int i=0;i<n;++i) nummax[ssz + i] = nums[i];
for (int i = ssz - 1; i > 0; --i) {
nummax[i] = max(nummax[2 * i], nummax[2 * i + 1]);
}
}
signed main(){
cin >> n;
nums.resize(n);
for(int i=0;i<n;++i){
cin >> nums[i];
}
// first, find the good ranges
// do this using a nextmax array
vector<int> nextmax(n, n);
stack<int> st;
for(int i=n-1;i>=0;--i){
while(!st.empty() && nums[st.top()] <= nums[i]) st.pop();
if (!st.empty()) nextmax[i] = st.top();
st.push(i);
}
vector<vector<pair<int,ll>>> good(n); // left, pivot, val
for(int left = 0;left < n-1;++left){
int right = left + 1;
do {
int pivot = 2*right - left;
if (pivot >= n) break;
good[left].push_back({pivot, nums[left] + nums[right]});
if (nums[right] >= nums[left]) break;
right = nextmax[right];
} while (right < n);
}
// print all the good triples
set_nummax();
// add at LEFT from PIVOT to end with VAL
// now load in the queries
vector<vector<pair<int,int>>> quers(n); // left, right, id
int q; cin >> q;
vector<pair<int,int>> lrvals(q);
vector<ll> ans(q, -INF); // answer for each query
for(int i=0;i<q;++i){
int l, r; cin >> l >> r; l--; r--;
quers[l].push_back({r, i});
lrvals[i] = {l, r};
}
for(int l = n-1;l>=0;--l){
// first, insert the necessary ranges
for(auto& [pivot, val] : good[l]) {
update(val, pivot, n-1, 1, 0, ssz-1);
}
// then, carry out the necessary queries
for(auto& [r, ind]:quers[l]){
ans[ind] = query(0, r, 1, 0, ssz-1);
}
}
/*
vector<ll> simple_ans(q, -INF);
for(int qq=0;qq<q;++qq){
int l = lrvals[qq].first, r = lrvals[qq].second;
for(int a=l;a<=r;++a){
for (int b = a+1;b<=r;++b){
for(int c = b+1; c <= r; ++ c){
if (c-b >= b-a) simple_ans[qq] = max(simple_ans[qq], nums[a] + nums[b] + nums[c]);
}
}
}
}*/
for (int i=0;i<q;++i){
cout << ans[i] <<endl;
}
}
