#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 2;
ll a[N + 2];
int b[N + 2];
int c[N + 2];
vector < pair < int , int > > query[N + 2];
ll st[4 * N + 2];
ll mx1[4 * N + 2];
ll mx2[4 * N + 2];
vector < int > d[N + 2];
vector < int > f[N + 2];
void update(int id , int l , int r , int post , ll val ){
if(l > post || r < post){
return;
}
if(l == r){
mx1[id] = max(mx1[id],a[l]);
mx2[id] = max(mx2[id],val);
st[id] = mx1[id] + mx2[id];
return ;
}
int mid = (l + r) / 2;
update(id * 2 , l , mid , post , val);
update(id * 2 + 1 , mid + 1 , r , post , val);
st[id] = max({st[id * 2 + 1] , st[id * 2] , mx2[id * 2] + mx1[id * 2 + 1]});
mx1[id] = max(mx1[id * 2] , mx1[id * 2 + 1]);
mx2[id ] = max(mx2[id * 2 + 1] , mx2[id * 2]);
}
pair < ll , pair <ll , ll > > get(int id , int l , int r ,int u , int v ){
if(l > v || r < u)return {0 , {0 , 0 }};
pair < ll , pair <ll , ll > > ans;
if(u <= l && r <= v){
return {st[id] , {mx1[id], mx2[id]}};
}
int mid =(l + r) /2;
auto[max1 , cur1] = get(id * 2 , l , mid ,u ,v);
auto[max2 , cur2] = get(id * 2 + 1 , mid + 1 , r ,u ,v);
ans.first = max({max1 , max2 , cur1.second + cur2.first});
ans.second.first = max(cur2.first, cur1.first);
ans.second.second = max(cur2.second ,cur1.second);
return ans;
}
ll res[N + 2];
void solve() {
int n ,q ;
cin >> n ;
stack< int > q1;
stack< int > q2;
for(int i = 1 ;i <= n ;i ++){
cin >> a[i];
}
q1.push(n + 1);
q2.push(n + 2);
a[n + 1] = INT64_MAX;
a[n + 2] = INT64_MIN;
for(int i = n ; i >= 1 ; i --){
while(a[q1.top()] < a[i])q1.pop();
while(a[q2.top()] >= a[i])q2.pop();
b[i] = q1.top();
c[i] = q2.top();
q1.push(i);
q2.push(i);
}
while(q1.size())q1.pop();
while(q2.size())q2.pop();
for(int i = 1; i <= n ;i ++){
while(q1.size() && a[q1.top()] < a[i])q1.pop();
while(q2.size()&& a[q2.top()] >= a[i])q2.pop();
if(q1.size())d[q1.top()].push_back(i);
if(q2.size())f[q2.top()].push_back(i);
q1.push(i);
q2.push(i);
}
cin >> q;
for(int i = 1; i <= q; i ++){
int l , r;
cin >> l >> r;
query[l].push_back({r , i});
}
for(int i = n ;i >= 1 ;i --){
update(1 , 1 , n , 2 * b[i] - i , a[i] + a[b[i]]);
update(1 , 1 , n , 2 * c[i] - i , a[i] + a[c[i]]);
for(auto vl : d[i]){
update(1 , 1 , n , 2 * vl - i , a[i] + a[vl]);
}
for(auto vl : f[i]){
update(1 , 1 , n , 2 * vl - i , a[i] + a[vl]);
}
for(auto[r , id] : query[i]){
res[id] = get(1 , 1 , n , i , r).first;
}
}
for(int i = 1; i <= q; i ++)cout << res[i] << "\n";
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
#define _ "digit."
if (fopen(_ "inp", "r")) {
freopen(_ "inp", "r", stdin);
freopen(_ "out", "w", stdout);
}
solve();
}
