#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;
bool cmp(const pii& x, const pii& y){
return x.second < y.second;
}
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;
}
vector<pii> get2(int L, int R, int K){
vector<pii> ans;
if(L > R) return ans;
vector<pii> m;
for(int it = 0; it < K; ++it){
pii t = get(1, 1, n, L, R);
if(t.second == -1 || t.first == 0) break;
ans.emplace_back(t.first, t.second);
m.emplace_back(t.second, t.first);
update(1, 1, n, t.second, 0);
}
for(auto p : m){
update(1, 1, n, p.first, p.second);
}
return ans;
}
void met(const pii& A, const pii& B, const pii& C, int ql){
if(A.second <= 0 || B.second <= 0 || C.second <= 0) return;
vector<pii> tmp;
tmp.push_back(A);
tmp.push_back(B);
tmp.push_back(C);
sort(tmp.begin(), tmp.end(), cmp);
int a_val = tmp[0].first, a_idx = tmp[0].second;
int b_val = tmp[1].first, b_idx = tmp[1].second;
int c_val = tmp[2].first, c_idx = tmp[2].second;
if(!(a_idx < b_idx && b_idx < c_idx)) return;
if((b_idx - a_idx) <= (c_idx - b_idx)){
res[ql] = max(res[ql], (int)(a_val + b_val + c_val));
}
}
void DnC(int l, int r, vector<query> qq){
if(r - l + 1 < 3 || qq.empty()) return;
int mid = (l + r) / 2;
vector<query> qleft, qright , tmp;
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){
auto L = get2(x.l, mid, 3);
auto R = get2(mid+1, x.r, 3);
if(L.size() >= 3){
for(int i = 0; i < L.size(); ++i)
for(int j = i+1; j < L.size(); ++j)
for(int k = j+1; k < L.size(); ++k)
met(L[i], L[j], L[k], x.idx);
}
if(R.size() >= 3){
for(int i = 0; i < R.size(); ++i)
for(int j = i+1; j < R.size(); ++j)
for(int k = j+1; k < R.size(); ++k)
met(R[i], R[j], R[k], x.idx);
}
for(int i = 0; i < L.size(); ++i)
for(int j = 0; j < L.size(); ++j){
if(i == j) continue;
if(L[i].second == L[j].second) continue;
for(int k = 0; k < R.size(); ++k){
met(L[i], L[j], R[k], x.idx);
}
}
for(int i = 0; i < L.size(); ++i)
for(int j = 0; j < R.size(); ++j)
for(int k = 0; k < R.size(); ++k){
if(j == k) continue;
if(R[j].second == R[k].second) continue;
met(L[i], R[j], R[k], x.idx);
}
}
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;
}
