#include<bits/stdc++.h>
#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"
using namespace std;
template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}
typedef long long ll;
typedef long double ld;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}
const int N = 2e5 + 15;
int n, q;
int a[N];
vector<int> candidates[N];
vector<pair<int,int>> query[N];
int ans[N];
struct SegmentTree{
struct node{
//i < j < k
//Two = max(a[i] + a[j)
//One = max(a[k])
int One, Two, Three;
node() : One(0), Two(0), Three(0) {}
node(int One, int Two, int Three) : One(One), Two(Two), Three(Three) {}
};
int n;
vector<node> st;
SegmentTree(int n) : n(n), st(n << 2) {}
node merge(node a, node b){
node c;
c.Three = max({a.Three, b.Three, a.Two + b.One});
c.One = max(a.One, b.One);
c.Two = max(a.Two, b.Two);
return c;
}
void update_one(int l, int r, int id, int pos, int v){
if(r < pos || l > pos) return;
if(l == r){
maximize(st[id].One, v);
maximize(st[id].Three, st[id].One + st[id].Two);
return;
}
int mid = (l+r) >> 1;
update_one(l,mid,id<<1,pos,v);
update_one(mid+1,r,id<<1|1,pos,v);
st[id] = merge(st[id<<1], st[id<<1|1]);
}
void update_two(int l, int r, int id, int pos, int v){
if(r < pos || l > pos) return;
if(l == r){
maximize(st[id].Two, v);
maximize(st[id].Three, st[id].One + st[id].Two);
return;
}
int mid = (l+r) >> 1;
update_two(l,mid,id<<1,pos,v);
update_two(mid+1,r,id<<1|1,pos,v);
st[id] = merge(st[id<<1], st[id<<1|1]);
}
node get(int l, int r, int id, int u, int v){
if(r < u || l > v) return node();
if(u <= l && r <= v) return st[id];
int mid = (l+r) >> 1;
return merge(get(l,mid,id<<1,u,v), get(mid+1,r,id<<1|1,u,v));
}
};
void solve(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
stack<int> ST;
auto add_candidates = [&](int i, int j) -> void{
if(2*j - i <= n) candidates[i].push_back(j);// cout << i << " " << j << endl;
};
for(int i = 1; i <= n; i++){
//cout << dbg(i) << endl;
while(!ST.empty() && a[ST.top()] <= a[i]){
//cout << "of 1: \n";
add_candidates(ST.top(), i);
ST.pop();
}
//cout << "of 2: \n";
if(!ST.empty()) add_candidates(ST.top(), i);
ST.push(i);
}
cin >> q;
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
query[l].push_back(pii(r,i));
}
SegmentTree st(n);
for(int i = n; i >= 1; i--){
st.update_one(1,n,1,i,a[i]);
for(int j : candidates[i]){
int k = 2*j - i;
st.update_two(1,n,1,k,a[i] + a[j]);
//cout << k << " " << a[i] + a[j] << endl;
//cout << "---" << endl;
}
for(auto [j, id] : query[i]){
ans[id] = st.get(1,n,1,i,j).Three;
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);
#define task "task"
if(fopen(task".INP", "r")){
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
int t; t = 1; //cin >> t;
while(t--) solve();
}
/*
i < j < k
+) j - i <= k - j
<=> 2*j - i <= k
<=> 2*j/i <= k
--> (i) is inversly proportional to (k)
for each i, find some important point j, update for range[k;n]
larger the i, larger range [k;n]
+) offline:
for(i : n -> 1) answer query with lb is (i)
+) consider query [L;R] with:
L <= x < y < z <= R
a[x] > a[y] > a[z]
z is not important to x:
a[x] + a[y] > a[x] + a[z] --> (x,y) is more valuable
y - x <= z - x --> (x,y) gives a better range of [k; r]
--> only pick (x,y) or (y,z)
--> use stack max from 1 -> n: match (i) with the back of the stack
*) 2*i - st.back() <= n --> (i) is important to st.back()
+) [L;mid] : max(a[i] + a[j])
[mid+1;R]: max(a[k])
--> segment tree merge nodes
*/
