#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first
#define vs second
const int mod = 1000000007;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct Seg{
vector<int> mx,ans;
vector<int> lazy;
int siz;
void init(int n){
siz = 1;
while(siz < n)siz*=2;
mx.assign(siz * 2 , 0);
ans.assign(siz * 2 , 0);
lazy.assign(siz * 2 , -1);
}
void push(int x){
lazy[2 * x + 1] = max(lazy[2 * x + 1] , lazy[x]);
lazy[2 * x + 2] = max(lazy[2 * x + 2] , lazy[x]);
ans[2 * x + 1] = max(ans[2 * x + 1] , lazy[2 * x + 1] + mx[2 * x + 1]);
ans[2 * x + 2] = max(ans[2 * x + 2] , lazy[2 * x + 2] + mx[2 * x + 2]);
lazy[x] = -1;
}
void build(vector<int>& a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < a.size()){
mx[x] = ans[x] = a[lx];
}
return;
}
int m = (lx + rx)/2;
build(a , 2 * x + 1 ,lx , m);
build(a , 2 * x + 2 , m , rx);
mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]);
ans[x] = max(ans[2 *x + 1] , ans[2 * x + 2]);
}
void build(vector<int>& a){
build(a , 0 , 0 , siz);
}
void set(int l , int r, int val, int x , int lx, int rx){
if(r <= lx || rx <= l)return;
if(lx >= l && rx <= r){
lazy[x] = max(lazy[x], val);
ans[x] = max(ans[x] , mx[x] + val);
return;
}
push(x);
int m = (lx + rx)/2;
set(l , r , val , 2 * x + 1, lx , m);
set(l , r , val , 2 * x + 2 , m , rx);
ans[x] = max(ans[2 * x + 1] , ans[2 * x + 2]);
}
void set(int l , int r , int val){
set(l , r , val , 0 , 0 , siz);
}
int range_op(int l , int r , int x , int lx, int rx){
if(rx <= l || r <= lx)return -1;
if(lx >= l && rx <= r){
return ans[x];
}
push(x);
int m = (lx + rx)/2;
return max(range_op(l , r , 2 * x + 1 , lx , m) , range_op(l , r , 2 * x + 2 , m , rx));
}
int range_op(int l ,int r){
return range_op(l , r , 0 , 0 ,siz);
}
};
void solve(){
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
Seg st;
st.init(n + 1);
st.build(a);
stack<int> stk;
vector<int> right[n + 1];
for(int i = 0; i < n; i++){
while(stk.size() && a[stk.top()] < a[i]){
stk.pop();
}
if(stk.size()){
//cout << stk.top() << ' ' << i << '\n';
right[stk.top()].pb(i);
}
stk.push(i);
}
while(stk.size())stk.pop();
for(int i = n - 1; i >= 0; i--){
while(stk.size() && a[stk.top()] < a[i]){
stk.pop();
}
if(stk.size()){
//cout << stk.top() << ' ' << i << '\n';
right[i].pb(stk.top());
}
stk.push(i);
}
int q;
cin >> q;
vector<pair<int,int>> queries[n + 1];
int ans[q];
for(int i = 0; i < q; i++){
int l , r;
cin >> l >> r;
l--;
r--;
queries[l].pb(mp(r , i));
}
for(int i = n - 1; i >= 0; i--){
for(int j : right[i]){
int r = j + (j - i);
if(r < n){
st.set(r , n , a[i] + a[j]);
}
}
for(auto j : queries[i]){
ans[j.vs] = st.range_op(i , j.vf + 1);
}
}
for(int i = 0; i < q; i++){
cout << ans[i] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;
//cin >> t;
//while(t--)
solve();
}
