#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = (1<<19) + 1;
int Mx1[N<<1], Mx2[N<<1], Mx3[N<<1], Arr[N], Ans[N];
vector<pair<int,int>> vec[N], rng;
void build(int cur = 1, int st = 1, int en = N){
if (en - st == 1){
Mx1[cur] = Arr[st];
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
build(lc, st, mid);
build(rc, mid, en);
Mx1[cur] = max(Mx1[lc], Mx1[rc]);
}
void Push(int cur, int lc, int rc){
Mx2[lc] = max(Mx2[lc], Mx2[cur]), Mx3[lc] = max(Mx3[lc], Mx2[lc] + Mx1[lc]);
Mx2[rc] = max(Mx2[rc], Mx2[cur]), Mx3[rc] = max(Mx3[rc], Mx2[rc] + Mx1[rc]);
}
void insert(int l, int r, int vl, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
Mx2[cur] = max(Mx2[cur], vl);
Mx3[cur] = max(Mx3[cur], Mx2[cur] + Mx1[cur]);
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc);
insert(l, r, vl, lc, st, mid);
insert(l, r, vl, rc, mid, en);
Mx3[cur] = max(Mx3[lc], Mx3[rc]);
}
int get(int l, int r, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return 0;
if (l <= st and r >= en)
return Mx3[cur];
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc);
return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, q;
cin>>n;
vector<int> vc, Vc;
for (int i=1;i<=n;i++){
cin>>Arr[i];
while (vc.size() > 0 and Arr[vc.back()] <= Arr[i])
rng.push_back({vc.back(), i}), vc.pop_back();
vc.push_back(i);
}
for (int i=n;i>=1;i--){
while (Vc.size() > 0 and Arr[Vc.back()] <= Arr[i])
rng.push_back({i, Vc.back()}), Vc.pop_back();
Vc.push_back(i);
}
sort(rng.begin(), rng.end());
build();
cin>>q;
for (int i=1;i<=q;i++){
int l, r;
cin>>l>>r;
vec[l].push_back({r, i});
}
for (int i=n;i>=1;i--){
while (rng.size() > 0 and rng.back().first >= i){
auto [a, b] = rng.back();
rng.pop_back();
insert(2 * b - a, N, Arr[a] + Arr[b]);
}
for (auto [r, id] : vec[i])
Ans[id] = get(i + 2, r + 1);
}
for (int i=1;i<=q;i++)
cout<<Ans[i]<<'\n';
}
