#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 5e5+10;
const int INF = INT_MAX;
const int mod = 1e9+7;
int n,a[N];
int t;
vector<pair<int,int>> q[N];
stack<int> st;
ll ans[N],lazy[4*N];
struct Node{
ll best,mx,Mx;
Node() {};
Node(ll _best, ll _mx, ll _Mx) {
best = _best;
mx = _mx;
Mx = _Mx;
};
}tree[4*N];
Node operator + (Node u, Node v) {
Node res = u;
res.best = max({res.best,u.mx+v.Mx,v.best});
res.mx = max(res.mx,v.mx);
res.Mx = max(res.Mx,v.Mx);
return res;
}
void build(int id = 1, int l = 1, int r = n) {
if(l == r) {
tree[id].Mx = a[l];
tree[id].best = a[l];
return;
}
int mid = l + r >> 1;
build(id << 1,l,mid);
build(id << 1 | 1,mid+1,r);
tree[id] = tree[id << 1] + tree[id << 1 | 1];
}
void down(int id, int l, int r) {
ll t = lazy[id];
if(t == 0) {
return;
}
tree[id].mx = max(tree[id].mx,t);
tree[id].best = tree[id].mx+tree[id].Mx;
if(l < r) {
lazy[id << 1] = max(lazy[id << 1],t);
lazy[id << 1 | 1] = max(lazy[id << 1 | 1],t);
}
t = 0;
}
void update(int pos, ll val, int id = 1, int l = 1, int r = n) {
// down(id,l,r);
// if(pos > n) {
// re
// }
if(l == r) {
tree[id].mx = max(tree[id].mx,val);
tree[id].best = tree[id].mx + tree[id].Mx;
return;
}
int mid = l + r >> 1;
if(pos <= mid) {
update(pos,val,id << 1,l,mid);
}
else {
update(pos,val,id << 1 | 1,mid+1,r);
}
tree[id] = tree[id << 1] + tree[id << 1 | 1];
}
Node get(int u, int v, int id = 1, int l = 1, int r = n) {
if(u > v || l > r || r < u || v < l) {
return {0,0,0};
}
if(u <= l && r <= v) {
return tree[id];
}
int mid = l + r >> 1;
return get(u,v,id << 1,l,mid)+get(u,v,id << 1 | 1,mid+1,r);
}
signed main()
{
if (fopen("triplejump.inp", "r")) {
freopen("triplejump.inp", "r", stdin);
freopen("triplejump.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
cin >> t;
for(int i = 1 ; i <= t ; i++) {
int l,r; cin >> l >> r;
q[l].push_back({r,i});
}
build();
for(int i = n ; i > 0 ; i--) {
while(!st.empty() && a[st.top()] < a[i]) {
if(2*st.top()-i <= n) {
update(2*st.top()-i,a[i]+a[st.top()]);
}
st.pop();
}
if(!st.empty()) {
if(2*st.top()-i <= n) {
update(2*st.top()-i,a[i]+a[st.top()]);
}
}
st.push(i);
for(auto p:q[i]) {
ans[p.second] = get(i,p.first).best;
}
}
for(int i = 1 ; i <= t ; i++) {
cout << ans[i] << '\n';
}
return 0;
}
