#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
#define usa unsigned int
#define pirusa pair <unsigned int,unsigned int>
using namespace std;
const int maxn = 5e5 + 5;
template <typename T> void maxi(T &x,T y){x = max(x,y);}
struct segment_tree{
unsigned int seg[4*maxn],lazy[4*maxn],base[4*maxn];
void downlazy(int v,int l,int r){
if (!lazy[v]) return;
seg[v] = max(seg[v],base[v] + lazy[v]);
if (l != r){
maxi(lazy[2*v + 1],lazy[v]);
maxi(lazy[2*v + 2],lazy[v]);
}
lazy[v] = 0;
}
void base_update(int l,int r,int v,int p,int val){
if (l > p || r < p) return;
if (l == r){
base[v] = val;
return;
}
int w = (l + r)/2;
base_update(l,w,2*v + 1,p,val);
base_update(w + 1,r,2*v + 2,p,val);
base[v] = max(base[2*v + 1],base[2*v + 2]);
}
void update(int l,int r,int v,int lx,int rx,unsigned int val){
downlazy(v,l,r);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx){
lazy[v] = max(lazy[v],val);
downlazy(v,l,r);
return;
}
int w = (l + r)/2;
update(l,w,2*v + 1,lx,rx,val);
update(w + 1,r,2*v + 2,lx,rx,val);
seg[v] = max(seg[2*v + 1],seg[2*v + 2]);
}
unsigned int calc(int l,int r,int v,int lx,int rx){
downlazy(v,l,r);
if (l > rx || r < lx) return 0;
if (l >= lx && r <= rx) return seg[v];
int w = (l + r)/2;
return max(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
}
} seg;
vector <vector<pirusa>> vec(maxn);
usa res[maxn];
int a[maxn],L[maxn],R[maxn];
vector <vector<pir>> Q(maxn);
////////
int input(int n){
int q;
for (int i = 1 ; i <= n ; i++) cin >> a[i];
cin >> q;
for (int i = 1 ; i <= q ; i++){
cin >> L[i] >> R[i];
}
return q;
}
namespace sub1{
const int N = 5e3 + 5;
bool check(int n,int q){
return (n <= 5000);
}
unsigned int f[N][N];
void prepare(int n){
for (int l = 1 ; l < n - 1 ; l++){
int x = a[l + 1];
for (int r = l + 2 ; r <= n ; r++){
x = max(x,a[(l + r)/2]);
f[l][r] = max(f[l][r],(unsigned int)(a[l] + x + a[r]));
}
}
for (int len = 3 ; len <= n ; len++)
for (int i = 1 ; i <= n - len + 1 ; i++){
int l = i,r = i + len - 1;
f[l][r] = max(f[l][r],max(f[l + 1][r],f[l][r - 1]));
}
}
void solve(int n,int q){
prepare(n);
for (int i = 1 ; i <= q ; i++)
cout << f[L[i]][R[i]] << "\n";
}
}
///////
void prepare(int n){
deque <int> dq;
for (int i = n ; i > 0 ; i--){
while (dq.size()){
int l = i,r = dq.back();
if (2*r - l <= n)
vec[l].push_back({2*r - l,(usa)a[i] + (usa)a[dq.back()]});
if (a[dq.back()] <= a[i])
dq.pop_back();
else break;
}
dq.push_back(i);
}
for (int i = 1 ; i <= n ; i++)
seg.base_update(1,n,0,i,a[i]);
}
void prepare_query(int q){
for (int i = 1 ; i <= q ; i++)
Q[L[i]].push_back({R[i],i});
}
void solve(int n,int q){
for (int i = n ; i > 0 ; i--){
for (pirusa P : vec[i]){
int l = P.fi;usa val = P.se;
seg.update(1,n,0,l,n,val);
}
for (pir query : Q[i]){
int l = i,r = query.fi,id = query.se;
res[id] = seg.calc(1,n,0,l,r);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("JUMP.inp","r",stdin);
// freopen("JUMP.out","w",stdout);
int n,q;
cin >> n;
q = input(n);
if (sub1::check(n,q)){
sub1::solve(n,q);
return 0;
}
prepare(n);
prepare_query(q);
solve(n,q);
for (int i = 1 ; i <= q ; i++) cout << res[i] << "\n";
return 0;
}
