#include<bits/stdc++.h>
#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"
using namespace std;
template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}
typedef long long ll;
typedef long double ld;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}
const int N = 5e5 + 15;
int n, q;
int a[N];
int L[N], R[N];
namespace subtask1{
bool check(void){
return n <= 100 && q <= 100;
}
void main(){
for(int i = 1; i <= q; i++){
int res = 0;
for(int x = L[i]; x <= R[i]; x++){
for(int y = x+1; y <= R[i]; y++){
for(int z = 2*y - x; z <= R[i]; z++){
int sum = a[x] + a[y] + a[z];
maximize(res, sum);
}
}
}
cout << res << endl;
}
}
}
namespace subtask4{
// j - i <= k - j
// 2*j - i <= k
vector<pii> candidates[N];
void add(int i, int j){
if(2*j - i <= n) candidates[i].emplace_back(2*j - i, a[i] + a[j]);
}
struct node{
int best, one, two;
node() : best(0), one(0), two(0) {}
node(int best, int one, int two) : best(best), one(one), two(two) {}
friend node operator + (const node& a, const node& b){
node c;
c.one = max(a.one, b.one);
c.two = max(a.two, b.two);
c.best = max({a.best, b.best, a.two + b.one});
return c;
}
} st[N << 2];
void update(int l, int r, int id, int pos, int v, int t){
if(r < pos || l > pos) return;
if(l == r){
if(!t) maximize(st[id].one, v);
else maximize(st[id].two, v);
maximize(st[id].best, st[id].one + st[id].two);
return;
}
else{
int mid = (l+r) >> 1;
if(pos <= mid) update(l, mid, id<<1, pos, v, t);
else update(mid+1, r, id<<1|1, pos, v, t);
st[id] = st[id<<1] + st[id<<1|1];
}
}
node get(int l, int r, int id, int u, int v){
if(r < u || l > v) return node();
if(u <= l && r <= v) return st[id];
int mid = (l+r) >> 1;
return get(l, mid, id<<1, u, v) + get(mid+1, r, id<<1|1, u, v);
}
void upd(int pos, int v, int t){
update(1, n, 1, pos, v, t);
}
int query(int l, int r){
return get(1, n, 1, l, r).best;
}
vector<pii> qu[N];
int ans[N];
void main(){
stack<int> stk;
for(int i = 1; i <= n; i++){
while(!stk.empty() && a[stk.top()] <= a[i]){
add(stk.top(), i);
stk.pop();
}
// nearest j which a[j] > a[i] match (a[j] + a[i])
// since if a[l] > a[j] > a[i], opt for l will be j
if(!stk.empty()) add(stk.top(), i);
stk.push(i);
}
for(int i = 1; i <= q; i++){
qu[L[i]].emplace_back(R[i], i);
}
for(int i = n; i >= 1; i--){
for(auto e : candidates[i]){
upd(e.fi, e.se, 1);
}
upd(i, a[i], 0);
for(auto e : qu[i]){
ans[e.se] = query(i, e.fi);
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> q;
for(int i = 1; i <= q; i++){
cin >> L[i] >> R[i];
}
/*if(subtask1::check()) subtask1::main();
else*/ subtask4::main();
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(0); cout.tie(0);
#define task "task"
if(fopen(task".INP", "r")){
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
int t; t = 1; //cin >> t;
while(t--) solve();
}
