#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define xn '\n'
#define pb push_back
#define oo LONG_MAX
using namespace std;
typedef pair<ll,ll> i2;
typedef pair<ll,i2> i3;
typedef pair<i2,ll> i4;
const int N = 1e6+5;
const int M = 1e3+5;
const ll mo = 1e9+7;
ll n,m;
ll a[N];
i2 t[4*N];
void build(ll id,ll l,ll r){
if (l == r){
t[id].fi = a[l];
t[id].se = l;
return;
}
ll m = l + r >> 1;
build(id*2,l,m);
build(id*2+1,m+1,r);
t[id] = max(t[id*2],t[id*2+1]);
}
i2 get(ll id,ll l,ll r,ll u,ll v){
if (u > r || v < l) return {-1e9,0};
if (u <= l && r <= v) return t[id];
ll m = l + r >> 1;
return max(get(id*2,l,m,u,v),get(id*2+1,m+1,r,u,v));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (long i=1; i<=n; i++) cin >> a[i];
cin >> m;
build(1,1,n);
while (m--){
ll res = 0;
ll u,v; cin >> u >> v;
for (long i=u; i<=v; i++){
i2 max1 = get(1,1,n,u,i-1);
i2 max2 = get(1,1,n,i+(i-max1.se+1)-1,v);
res = max(res,a[i] + max1.fi + max2.fi);
}
cout << res << xn;
}
return 0;
}
