#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
const int N = 5e5 + 5;
pii st[4 * N];
int a[N];
struct query{
int l , r , idx;
};
int res[N];
vector<query> queries;
int n , q;
void build(int idx , int l , int r){
if(l == r){
st[idx].first = a[l];
st[idx].second = l;
return;
}
int mid = (l + r) / 2;
build(2 * idx , l , mid);
build(2 * idx + 1 , mid + 1 , r);
if(st[2 * idx].first >= st[2 * idx + 1].first) st[idx] = st[2 * idx];
else st[idx] = st[2 * idx + 1];
}
void update(int idx , int l , int r , int pos , int val){
if(l > pos || r < pos) return;
if(l == r){
st[idx].first = val;
return;
}
int mid = (l + r) / 2;
update(2 * idx , l , mid , pos , val);
update(2 * idx + 1 , mid + 1 , r , pos , val);
if(st[2 * idx].first >= st[2 * idx + 1].first) st[idx] = st[2 * idx];
else st[idx] = st[2 * idx + 1];
}
pii get(int idx , int l , int r , int u , int v){
if(l > v || r < u) return {0 , -1};
if(u <= l && r <= v) return st[idx];
int mid = (l + r) / 2;
pii t1 = get(2 * idx , l , mid , u , v);
pii t2 = get(2 * idx + 1 , mid + 1 , r , u , v);
if(t1.first >= t2.first) return t1;
else return t2;
}
void DnC(int l , int r , vector<query> qq){
if(r - l + 1 < 3 || qq.size() == 0) return;
int mid = (l + r) / 2;
vector<query> tmp , qleft , qright;
for(auto x : qq){
if(x.r < mid) qleft.push_back(x);
else if(x.l > mid) qright.push_back(x);
else tmp.push_back(x);
}
for(auto x : tmp){
pii u = get(1 , 1 , n , x.l , mid);
update(1, 1 , n , u.second , 0LL);
pii v = get(1 , 1 , n , x.l , mid);
pii z = get(1 , 1 , n , mid + 1 , x.r);
res[x.idx] = u.first + v.first + z.first;
update(1 , 1 , n , u.second , u.first);
u = get(1 , 1 , n , x.l , mid);
update(1 , 1 , n , u.second , 0);
v = get(1 , 1 , n , x.l , mid);
update(1 , 1 , n , v.second , 0);
z = get(1 , 1 , n , x.l , mid);
if(mid - x.l + 1 >= 3) res[x.idx] = max(res[x.idx] , u.first + v.first + z.first);
update(1 , 1, n , u.second , u.first);
update(1 , 1 , n , v.second , v.first);
u = get(1 , 1 , n , mid + 1 , x.r);
update(1 , 1 , n , u.second , 0);
v = get(1 , 1 , n , mid + 1 , x.r);
update(1 , 1 , n , v.second , 0);
z = get(1 , 1 , n , mid + 1 , x.r);
if(x.r - mid + 1 >= 3) res[x.idx] = max(res[x.idx] ,u.first + v.first + z.first);
update(1 , 1, n , u.second , u.first);
update(1 , 1 , n , v.second , v.first);
u = get(1 , 1 , n , mid + 1 , x.r);
update(1 , 1 , n , u.second , 0);
v = get(1 , 1 , n , mid + 1 , x.r);
update(1 , 1 , n , v.second , 0);
int dist = max(v.second , u.second) - min(v.second , u.second);
z = get(1 , 1 , n , max(min(v.second , u.second) - dist , x.l) , max(min(v.second , u.second) - 1 , x.l));
res[x.idx] = max(res[x.idx] ,u.first + v.first + z.first);
update(1 , 1, n , u.second , u.first);
update(1 , 1 , n , v.second , v.first);
}
DnC(l , mid - 1 , qleft);
DnC(mid + 1 , r , qright);
}
void solve(void){
cin >> n; for(int i = 1; i <= n ; i++) cin >> a[i];
cin >> q;
for(int i = 1 ; i <= q; i++){
int l , r; cin >> l >> r;
queries.push_back({l , r , i});
}
build(1 , 1 , n);
DnC(1 , n , queries);
for(int i = 1 ; i <= q ; i++){
cout << res[i] << endl;
}
}
signed main(void){
ios_base :: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
solve();
return 0;
}
