/*
it could have been better :)
it will next time ;)
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1e18
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>
const int MOD = 1'000'000'000 + 7;
void setIO(string name = "")
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#ifdef LOCAL
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#else
if (!name.empty())
{
freopen((name + ".INP").c_str(), "r", stdin);
freopen((name + ".OUT").c_str(), "w", stdout);
}
#endif
}
const int MAXN = 5e5;
int n, Q;
int a[MAXN + 5];
vector<pii> queries;
struct Event {
int type; // 0: add, 1: query
int l, r;
int id;
Event(int l, int r): type(0), l(l), r(r) {}
Event(int l, int r, int id): type(1), l(l), r(r), id(id) {}
bool operator<(const Event &other) {
if(l == other.l) return type < other.type;
return l > other.l;
}
};
int ans[MAXN + 5];
struct Node {
pii val;
int lazy;
} st[4 * MAXN + 5];
void down(int id, int l, int r) {
if(st[id].lazy == 0) return;
st[id].val.f = max(st[id].val.f, st[id].val.s + st[id].lazy);
if(l != r) {
st[id * 2].lazy = max(st[id * 2].lazy, st[id].lazy);
st[id * 2 + 1].lazy = max(st[id * 2 + 1].lazy, st[id].lazy);
}
st[id].lazy = 0;
}
void build(int id, int l, int r) {
if(l == r) {
st[id].val = {0, a[l]};
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id].val.s = max(st[id * 2].val.s, st[id * 2 + 1].val.s);
}
int query(int id, int l, int r, int u, int v) {
down(id, l, r);
if(v < l || r < u) return -INF;
if(u <= l && r <= v) return st[id].val.f;
int mid = (l + r) / 2;
return max(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
}
void upd(int id, int l, int r, int u, int v, int k) {
down(id, l, r);
if(v < l || r < u) return;
if(u <= l && r <= v) {
st[id].lazy = max(st[id].lazy, k);
down(id, l, r);
return;
}
int mid = (l + r) / 2;
upd(id * 2, l, mid, u, v, k);
upd(id * 2 + 1, mid + 1, r, u, v, k);
st[id].val.f = max(st[id * 2].val.f, st[id * 2 + 1].val.f);
st[id].val.s = max(st[id * 2].val.s, st[id * 2 + 1].val.s);
}
void solve()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> Q;
vector<Event> events;
for(int i = 1; i <= Q; i++) {
int l, r; cin >> l >> r;
events.push_back({l, r, i});
}
{
vi stk;
for(int i = n; i >= 1; i--) {
while(!stk.empty() && a[i] > a[stk.back()]) {
events.push_back(Event(i, stk.back()));
stk.pop_back();
}
if(!stk.empty()) {
events.push_back(Event(i, stk.back()));
// cout << i << ' ' << x << '\n';
}
stk.push_back(i);
}
}
build(1, 1, n);
sort(events.begin(), events.end());
for(auto e : events) {
// cout << e.type << ' ' << e.l << ' ' << e.r << '\n';
if(e.type == 0) {
if(2 * e.r - e.l <= n) {
upd(1, 1, n, 2 * e.r - e.l, n, a[e.l] + a[e.r]);
}
}
else {
ans[e.id] = query(1, 1, n, e.l, e.r);
}
}
for(int i = 1; i <= Q; i++) cout << ans[i] << '\n';
}
signed main()
{
setIO();
int t = 1;
// cin >> t;
while (t--)
solve();
}
