#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;
void GG(){cout<<"0\n"; exit(0);}
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
ll re=1;
while (n>0){
if (n&1) re = re*a %mo;
a = a*a %mo;
n>>=1;
}
return re;
}
ll inv (ll b, ll mo = mod){
if (b==1) return b;
return (mo-mo/b) * inv(mo%b,mo) % mo;
}
const int maxn = 1e5+5;
struct RMQ{
int seg[2 * maxn];
void build() { // build the tree
for (int i = maxn - 1; i > 0; --i) seg[i] = max(seg[i<<1] , seg[i<<1|1]);
}
void modify(int p, int value) { // set value at position p
for (seg[p += maxn] = value; p > 1; p >>= 1) seg[p>>1] = max(seg[p] , seg[p^1]);
}
int query(int l, int r) { // sum on interval [l, r)
int res = 0;
for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
if (l&1) res = max(res, seg[l++]);
if (r&1) res = max(res, seg[--r]);
}
return res;
}
RMQ(){
memset(seg, 0, sizeof seg);
}
};
int a[maxn];
struct EV{
int l, r, v;
};
struct QUE{
int l,r,i;
};
RMQ ar, dp;
struct QQ{
int i, v, mx;
bool operator < (const QQ &b) const {return i!=b.i?i<b.i:v>b.v;}
};
vector<QQ> here [maxn];
ll bg[maxn];
set<QQ> nowqq;
void upd(int i) {
for (QQ x : here[i]) {
// add x
if (x.v > bg[x.i]) {
bg[x.i] = x.v;
}else continue;
auto it = nowqq.insert(x).f;
bug("HI");
if (it != nowqq.begin() && prev(it)->v >= x.v) {
nowqq.erase(it); continue;
}
if (it != nowqq.begin()) {
dp.modify(prev(it)->i, prev(it) -> v + ar.query(prev(it)->i, x.i));
}
bug("HI");
it = next(it);
while (it->v <= x.v){
dp.modify(it->i, 0);
it = nowqq.erase(it);
}
bug("HI");
x.mx = ar.query(x.i, it->i);
dp.modify(x.i, x.v + x.mx);
bug("HI");
}
}
ll QU(int i) {
auto fs = prev(nowqq.upper_bound({i, -1, 0}));
ll re = ar.query(fs->i, i+1) + fs->v; // inclusive
re = max(re, dp.query(0, fs->i));
return re;
}
signed main(){
IOS();
int n; cin>>n;
vector<EV> lines;
{
vector<pii> tt;
for (int i = 0; i<n; ++i) {
cin>>a[i]; tt.pb({-a[i],i}); ar.modify(i,a[i]);
}
sort(ALL(tt));
set<int> tmps;
for (auto & p : tt) {
int i = p.s;
auto it = tmps.insert(i).f;
if (i != *tmps.rbegin()) {
int j = *next(it);
lines.pb({i, j + j-i, a[i] + a[j]});
}
if (i != *tmps.begin()) {
int j = *prev(it);
lines.pb({j, i + i-j, a[i] + a[j]});
}
}
// return 0;
}
for (auto & l : lines) {bug(l.l, l.r, l.v);}
lines.clear();
for (int i = 0; i<n; ++i) for (int j = i+1; j<n; ++j) lines.pb({i,j-i+j,a[i] + a[j]});
for (auto xx : lines) {
if (xx.r < n)
here[xx.l] . pb({xx.r, xx.v, -1});
}
// return 0;
int numq; cin>>numq;
vector<QUE> qlist;
for (int i = 0; i<numq; ++i) {
int l,r; cin>>l>>r;
qlist.pb({l-1,r-1,i});
}
nowqq.insert({n,1000000000,0});
sort(ALL(qlist),[&](QUE a, QUE b){return a.l > b.l;});
int nowl = n;
vector<int> ans(numq);
// return 0;
for (QUE q : qlist) {
bug(q.l);
while (nowl > q.l) {
upd(--nowl);
}
ans[q.i] = QU(q.r);
}
for (int x : ans) {
cout<<x<<endl;
}
}
