#include <bits/stdc++.h>
#define Y8o "Triple Jump"
#define maxn 500005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
#define f first
#define s second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
if(fopen(Y8o".inp", "r"))
{
freopen(Y8o".inp", "r", stdin);
// freopen(Y8o".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
int n, Q, q[maxn], nex[maxn];
ll a[maxn], ans[maxn];
vector<pair<int, int>> P;
struct dl {
int f, s, id;
bool operator < (const dl & other)
const {
if(f == other.f) return s < other.s;
return f < other.f;
}
} qr[maxn];
struct SEGTREE {
struct dl {
int ma, le, ri;
} st[4 * maxn];
dl cb(dl x, dl y)
{
dl best;
best.le = max(x.le, y.le);
best.ri = max(x.ri, y.ri);
best.ma = max({ x.ma, y.ma, x.le + y.ri });
return best;
}
void update(int i, ll val, int id = 1, int l = 1, int r = n) {
if(i < l || r < i) return ;
if(l == r) {
st[id] = {val + a[l], val, a[l]};
return ;
}
int mid = (l + r) >> 1;
update(i, val, id * 2, l, mid), update(i, val, id * 2 + 1, mid + 1, r);
st[id] = cb(st[id * 2], st[id * 2 + 1]);
}
dl get(int u, int v, int id = 1, int l = 1, int r = n) {
if(v < l || r < u) return {0, 0, 0};
if(u <= l && r <= v) return st[id];
int mid = (l + r) >> 1;
return cb( get(u, v, id * 2, l, mid), get(u, v, id * 2 + 1, mid + 1, r) );
}
} ST;
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
int d = 1, c = 0;
for(int i = 1; i <= n; i ++)
{
while(d <= c && a[i] >= a[q[c]]) P.push_back({ q[c], i }), c --;
if(c) P.push_back({ q[c], i });
q[++ c] = i;
}
sort(P.begin(), P.end());
//
for(int i = P.size() - 1; i >= 0; i --)
{
int u, v, val, id; tie(u, v) = P[i];
id = 2 * v - u, val = ST.get(id, id).le;
nex[i] = val, ST.update( id, max(1ll * val, a[u] + a[v]) );
}
cin >> Q;
for(int i = 1; i <= Q; i ++) cin >> qr[i].f >> qr[i].s, qr[i].id = i;
sort(qr + 1, qr + Q + 1);
int j = 0;
for(int i = 1; i <= Q; i ++)
{
int l = qr[i].f, r = qr[i].s, id = qr[i].id;
while(l > P[j].f) {
int u, v; tie(u, v) = P[j];
ST.update(2 * v - u, nex[j]);
j ++;
}
ans[id] = ST.get(l, r).ma ;
}
for(int i = 1; i <= Q; i ++) cout << ans[i] << '\n';
}
int main()
{
iof();
int nTest = 1;
// cin >> nTest;
while(nTest --) {
solve();
}
ctime();
return 0;
}
