/***
Todo:
If we fix A, then B should be the next element to the right which is > A
Same thing happens if we fix B.
So stack to find the closest greater left and right.
After that do something with C?
***/
#include<bits/stdc++.h>
#define left owo
#define right uwu
using namespace std;
const int N = 4002000;
const int MAXN = 500050;
struct SegmentTree{
int ans[N];
int best[N];
int lazy[N];
#define mid ((l + r) >> 1)
SegmentTree() {
for(int i = 0; i < N; ++i) ans[i] = best[i] = (int)-1e9;
}
void push(int x) {
ans[x] = max(ans[x], best[x] + lazy[x]);
lazy[x << 1] = max(lazy[x << 1], lazy[x]);
lazy[x << 1 | 1] = max(lazy[x << 1 | 1], lazy[x]);
lazy[x] = 0;
return;
}
void modify(int x, int l, int r, int pos, int val) {
push(x);
if(l == r) {
best[x] = max(best[x], val);
return;
}
if(pos <= mid) modify(x << 1, l, mid, pos, val);
else modify(x << 1 | 1, mid + 1, r, pos, val);
best[x] = max({best[x], best[x << 1], best[x << 1 | 1]});
ans[x] = max({ans[x], ans[x << 1], ans[x << 1 | 1]});
return;
}
int query(int x, int l, int r, int pos) {
push(x);
if(r < pos) return -1;
if(l >= pos){
//cout << l << " " << r << " " << ans[x] << endl;
return ans[x];
}
int ret = max(query(x << 1, l, mid, pos), query(x << 1 | 1, mid + 1, r, pos));
ans[x] = max({ans[x], ans[x << 1], ans[x << 1 | 1]});
return ret;
}
#undef mid
}seg;
int n, q;
int a[MAXN];
int left[MAXN];
int right[MAXN];
int answer[MAXN];
vector<pair<int, int>> queries[MAXN];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; ++i) cin >> a[i];
vector<int> st;
for(int i = 0; i < n; ++i) {
while(!st.empty() && a[i] >= a[st.back()]) {
right[st.back()] = i;
st.pop_back();
}
if(!st.empty()) left[i] = st.back();
else left[i] = -1;
st.push_back(i);
}
while(!st.empty()) {
right[st.back()] = -1;
st.pop_back();
}
cin >> q;
for(int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
queries[--r].emplace_back(--l, i);
}
set<pair<int, int>> que;
//b - a <= c - b -> 2b - a <= c
for(int i = 0; i < n; ++i) {
if(right[i] != -1) {
que.emplace(2 * right[i] - i, i);
}
if(left[i] != -1) {
que.emplace(2 * i - left[i], i + MAXN);
}
while(!que.empty() && que.begin() -> first <= i) {
auto p = *que.begin(); que.erase(que.begin());
int x, y;
if(p.second >= MAXN) {
p.second -= MAXN;
x = left[p.second];
y = p.second;
}
else {
x = p.second;
y = right[p.second];
}
seg.modify(1, 0, n - 1, x, a[x] + a[y]);
}
/// update on IT as C = a[i]
seg.lazy[1] = max(seg.lazy[1], a[i]);
/// answer for queries
for(auto q : queries[i]) {
answer[q.second] = seg.query(1, 0, n - 1, q.first);
}
}
for(int i = 0; i < q; ++i) {
cout << answer[i] << "\n";
}
// chiu cha biet sai gi
return 0;
}
