#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int maxn = 1e6 + 100;
int n ,Q ,a[maxn], ans[maxn] ,sz = 1;
vector<pair<int ,int>> q[maxn];
vector<int> baze[maxn];
struct segment_tree{
int seg[maxn * 2], lazy[maxn * 2], maxi[maxn * 2];
segment_tree(){
for(int i = 0; i < maxn * 2; i++){
seg[i] = 0 ,lazy[i] = 0, maxi[i] = 0;
}
}
void build_max(){
for(int i = sz - 1; i >= 0 ;i--){
maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]);
}
}
void push(int v, int L, int R){
if(L == R) return;
lazy[v * 2] = max(lazy[v * 2], lazy[v]);
lazy[v * 2 + 1] = max(lazy[v * 2 + 1], lazy[v]);
seg[v * 2] = max(seg[v * 2], lazy[v] + maxi[v * 2]);
seg[2 * v + 1] = max(seg[2 * v + 1], lazy[v] + maxi[2 * v + 1]);
lazy[v] = 0;
}
void update(int v ,int L, int R ,int l, int r ,int val){
if(L > r or l > R){
return;
}
if(L >= l and R <= r){
seg[v] = max(seg[v] , val + maxi[v]);
lazy[v] = max(lazy[v], val);
return;
}
push(v ,L, R);
int mid = (R + L) / 2;
update(2 * v , L ,mid , l ,r, val);
update(2 * v + 1, mid + 1 ,R ,l, r, val);
seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}
int get(int v ,int L, int R ,int l, int r ){
if(L > r or l > R){
return 0;
}
if(l <= L and R <= r){
return seg[v];
}
push(v ,L, R);
int mid = (R + L) / 2;
return max(get(2 * v ,L , mid , l, r), get(2 * v + 1 ,mid + 1, R ,l ,r));
}
}seg;
int32_t main(){
ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);
cin >> n;
while(sz < n) sz *= 2;
for(int i = 0 ;i < n; i++){
cin >> a[i];
seg.maxi[i + sz] = a[i];
}
seg.build_max();
stack<pair<int,int>> s;
for(int i = 0; i < n; i++){
while(s.size() and s.top().first < a[i]){
baze[s.top().second].push_back(i);
s.pop();
}
if(s.size()) baze[s.top().second].push_back(i);
s.push({a[i], i});
}
cin >> Q;
for(int i = 0 ;i < Q; i++){
int l, r;
cin >> l >> r;
l--,r--;
q[l].push_back({r, i});
}
for(int i = n - 1; i >= 0 ; i--){
for(auto r : baze[i]){
int val = a[i] + a[r];
seg.update(1 , 0, sz - 1, 2 * r - i , n - 1, val);
}
for(auto x : q[i]){
int r = x.first, ind = x.second;
ans[ind] = seg.get(1 ,0 ,sz - 1 , i, r);
}
}
for(int i = 0 ; i < Q; i++){
cout << ans[i] << endl;
}
return 0;
}
