//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n , q , o[500000];
vector<int> a , ps[500000];
vector<arr(2)> ops[500000];
int seg[2000001][2] , seginf[2000001][2] , laz[2000001];
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
seginf[i][0] = l , seginf[i][1] = r , laz[i] = 0;
if(l == r) seg[i][0] = a[l];
else{
int c = (r + l - 1) >> 1;
buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
seg[i][0] = max(seg[i << 1][0] , seg[(i << 1) | 1][0]);
}
seg[i][1] = seg[i][0];
}
void pushSeg(int i){
for(int ch = (i << 1) ; ch <= ((i << 1) | 1) ; ch++){
seg[ch][1] = max(seg[ch][1] , seg[ch][0] + laz[i]);
laz[ch] = max(laz[ch] , laz[i]);
}
laz[i] = 0;
}
void addSeg(int l , int r , int i , int val){
if(seginf[i][0] >= l and seginf[i][1] <= r){
seg[i][1] = max(seg[i][1] , seg[i][0] + val);
laz[i] = max(laz[i] , val);
}else if(seginf[i][1] >= l and seginf[i][0] <= r){
pushSeg(i);
addSeg(l , r , i << 1 , val) , addSeg(l , r , (i << 1) | 1 , val);
seg[i][1] = max(seg[i << 1][1] , seg[(i << 1) | 1][1]);
}
}
int getSeg(int l , int r , int i){
if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[i][1];
if(seginf[i][1] >= l and seginf[i][0] <= r){
pushSeg(i);
return max(getSeg(l , r , i << 1) , getSeg(l , r , (i << 1) | 1));
}
return 0;
}
void init(){
stack<int> hds;
for(int i = 0 ; i < n ; i++){
while(!hds.empty() and a[hds.top()] <= a[i]){
ps[hds.top()].pb(i);
hds.pop();
}
if(!hds.empty()) ps[hds.top()].pb(i);
hds.push(i);
}
}
void f(){
for(int l = n - 1 ; l >= 0 ; l--){
for(int r : ps[l]){
int inx = r + r - l;
if(inx <= n - 1) addSeg(inx , n - 1 , 1 , a[l] + a[r]);
}
for(auto &op : ops[l]){
o[op[1]] = getSeg(l , op[0] , 1);
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0 ; i < n ; i++){
int d;
cin >> d;
a.pb(d);
}
cin >> q;
for(int i = 0 ; i < q ; i++){
int l , r;
cin >> l >> r;
l-- , r--;
ops[l].pb({r , i});
}
buildSeg() , init() , f();
for(int i = 0 ; i < q ; i++) cout << o[i] << endl;
}
