#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
int a[N], st[N * 4];
void build(int v, int l, int r){
if(l == r){
st[v] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(v * 2, l, mid);
build(v * 2 + 1, mid + 1, r);
st[v] = max(st[v * 2], st[v * 2 + 1]);
}
int ask(int v, int l, int r, int ql, int qr){
if(l > qr or r < ql)return 0;
if(l >= ql && r <= qr)return st[v];
int mid = (l + r) >> 1;
return max(ask(v * 2, l, mid, ql, qr), ask(v * 2 + 1, mid + 1, r, ql, qr));
}
signed main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
int mx = a[r], tot = 0;
for(int i = r - 1; i >= l; i--){
// cout << i << ':' << mx << '-' << a[i] << '-' << ask(1, 1, n, max(i - (r - i), l), i - 1) << endl;
tot = max(tot, mx + a[i] + ask(1, 1, n, max(i - (r - i), l), i - 1));
mx = max(mx, a[i]);
}
cout << tot << endl;
}
}
