#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define FOR(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define int long long
const ll INF = 1e18;
const int maxn = 5e5 + 5;
int n;
struct info{
int l, r, t, id;
info(){}
info(int _l, int _r, int _t, int _id) : l(_l), r(_r), t(_t), id(_id){}
bool operator < (const info& other) const{
if(l != other.l) return l < other.l;
return t < other.t;
}
bool operator > (const info& other) const{
if(l != other.l) return l > other.l;
return t > other.t;
}
};
struct node{
int f, mx, ttl, tag;
};
node st[maxn * 4];
void cast(int v, int val){
st[v].f = max(st[v].f, val);
st[v].tag = max(st[v].tag, val);
st[v].ttl = max(st[v].ttl, st[v].f + st[v].mx);
}
void push(int v){
if(st[v].tag){
cast(v * 2, st[v].tag);
cast(v * 2 + 1, st[v].tag);
st[v].tag = 0;
}
}
void upd(int l, int r, pll val, int v = 1, int L = 0, int R = n - 1){
if(l > R || r < L) return;
if(l <= L && r >= R){
st[v].f = max(st[v].f, val.f);
st[v].mx = max(st[v].mx, val.s);
st[v].tag = max(st[v].tag, val.f);
st[v].ttl = max(st[v].ttl, st[v].f + st[v].mx);
return;
}
push(v);
int m = (L + R) / 2;
upd(l, r, val, v * 2, L, m);
upd(l, r, val, v * 2 + 1, m + 1, R);
st[v].ttl = max(st[v * 2].ttl, st[v * 2 + 1].ttl);
st[v].mx = max(st[v * 2].mx, st[v * 2 + 1].mx);
}
int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
if(l > R || r < L) return 0;
if(l <= L && r >= R) return st[v].ttl;
push(v);
int m = (L + R) / 2;
return max(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
signed main(void){
fastio;
cin>>n;
for(int i = 0; i < n * 4; i++) st[i].f = st[i].mx = st[i].ttl = -INF;
vector<int> a(n);
for(int i = 0; i < n; i++) cin>>a[i];
int q;
cin>>q;
vector<pll> rng;
stack<int> stk;
stk.push(0);
for(int i = 1; i < n; i++){
while(!stk.empty() && a[stk.top()] <= a[i]){
rng.eb(stk.top(), i);
stk.pop();
}
if(!stk.empty()){
rng.eb(stk.top(), i);
}
stk.push(i);
}
vector<info> event;
for(auto [x, y] : rng){
// cout<<"ok : "<<x<<" "<<y<<"\n";
if(2 * y - x < n) event.pb(info(x, 2 * y - x, 1, a[x] + a[y]));
}
for(int i = 0; i < q; i++){
int l, r;
cin>>l>>r;
l--, r--;
event.pb(info(l, r, 0, i));
}
sort(event.begin(), event.end(), greater<info>());
for(int i = 0; i < n; i++) upd(i, i, {-INF, a[i]});
vector<int> ans(q);
for(int i = 0; i < event.size(); i++){
int t = event[i].l;
while(i < event.size() && event[i].l == t){
auto [l, r, t, id] = event[i];
// cout<<"event : "<<l<<" "<<r<<" "<<t<<" "<<id<<"\n";
i++;
if(t) upd(r, n - 1, {id, -INF});
else{
ans[id] = qry(l, r);
// cout<<"qry : "<<qry(l, r)<<"\n";
}
}
i--;
}
for(auto x : ans) cout<<x<<"\n";
cout<<"\n";
}
