#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int N = 5e5 + 1;
int n;
struct SegTree{
struct Info{
int opt, mx[2];
Info(){
opt = mx[0] = mx[1] = 0;
};
};
Info T[N * 4];
Info merge(Info L, Info R){
Info rt;
for ( auto j: {0, 1} ){
rt.mx[j] = max(L.mx[j], R.mx[j]);
}
rt.opt = max({L.opt, R.opt, L.mx[0] + R.mx[1]});
return rt;
}
void upd(int v, int l, int r, int p, int x, int j){
if ( l == r ){
chmax(T[v].mx[j], x);
chmax(T[v].opt, T[v].mx[0] + T[v].mx[1]);
return;
}
int md = (l + r) >> 1;
if ( p <= md ){
upd(v * 2, l, md, p, x, j);
} else{
upd(v * 2 + 1, md + 1, r, p, x, j);
}
T[v] = merge(T[v * 2], T[v * 2 + 1]);
}
void upd(int p, int x, int j = 0){
upd(1, 0, n - 1, p, x, j);
}
Info get(int v, int l, int r, int tl, int tr){
Info ret;
if ( l > tr or r < tl ){
return ret;
}
if ( tl <= l && tr >= r ){
return T[v];
}
int md = (l + r) >> 1;
return merge(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
}
int query(int l, int r){
return get(1, 0, n - 1, l, r).opt;
}
} seg;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
vector <int> a(n);
for ( auto &u: a ){
cin >> u;
}
vector <vector<int>> upd(n);
stack <int> stk;
for ( int i = 0; i < n; i++ ){
while ( !stk.empty() && a[stk.top()] < a[i] ){
stk.pop();
}
if ( !stk.empty() ){
upd[stk.top()].pb(i);
}
stk.push(i);
}
while ( stk.size() ) stk.pop();
for ( int i = n - 1; i >= 0; i-- ){
while ( !stk.empty() && a[stk.top()] < a[i] ){
stk.pop();
}
if ( !stk.empty() ){
upd[i].pb(stk.top());
}
stk.push(i);
}
int q; cin >> q;
vector <vector<ar<int,2>>> qu(n);
for ( int i = 0; i < q; i++ ){
int l, r; cin >> l >> r;
--l, --r;
qu[l].pb({i, r});
}
for ( int i = 0; i < n; i++ ){
seg.upd(i, a[i], 1);
}
vector <int> ans(q);
for ( int i = n - 1; i >= 0; i-- ){
for ( auto &j: upd[i] ){
if ( j * 2 - i < n ){
seg.upd(j * 2 - i, a[i] + a[j]);
}
}
for ( auto &[j, r]: qu[i] ){
ans[j] = seg.query(i, r);
}
}
for ( auto &u: ans ){
cout << u << ln;
}
cout << '\n';
}
