#include <bits/stdc++.h>
// Kazusa_Megumi
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;
#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif
const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;
int n, q, a[mn], val[mn << 2], st[mn << 2], lz[mn << 2], ans[mn];
void build(int id, int l, int r){
if(l == r){
val[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
val[id] = max(val[id << 1], val[id << 1 | 1]);
}
void down(int id, int l, int r){
if(!lz[id] || l == r) return;
lz[id << 1] = max(lz[id], lz[id << 1]);
st[id << 1] = max(st[id << 1], val[id << 1] + lz[id]);
lz[id << 1 | 1] = max(lz[id], lz[id << 1 | 1]);
st[id << 1 | 1] = max(st[id << 1 | 1], val[id << 1 | 1] + lz[id]);
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u) return;
if(l >= u && r <= v){
lz[id] = max(lz[id], x);
st[id] = max(st[id], val[id] + x);
return;
}
down(id, l, r);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, x);
update(id << 1 | 1, mid + 1, r, u, v, x);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v){
if(l > v || r < u) return 0;
if(l >= u && r <= v) return st[id];
down(id, l, r);
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
vector <pii> query[mn];
vector <int> line[mn];
/*
Nhận xét 1: Cho các bộ ba (i, j, a), chỉ xét các cặp (i, j) sao cho max[i + 1 -> j - 1] < min(a[i], a[j])
Chứng minh:
Nếu tồn tại k mà (i < k < j) sao cho (i, k) hoặc (j, k) tốt hơn (i, j) thì sai do
*) Vấn đề về khoảng cách j - i <= a - j, do thay k vào i hoặc j thì khoảng cách từ a tăng còn bên kia giảm
=> luôn thỏa mãn
*) Vấn đề về giá trị, do a[k] < min(a[j], a[i])
=> ko thỏa mãn
=> dpcm
Nhận xét 2: Số cặp (i, j) cần xét như trên chỉ có tối đa là O(2 * n) cặp
Chứng minh: dùng stack cơ bản
*/
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
cin >> q;
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
query[l].push_back({r, i});
}
stack <int> s;
for(int i = 1; i <= n; i++){
while(s.size() && a[s.top()] <= a[i]){
line[s.top()].push_back(i);
s.pop();
}
if(s.size()) line[s.top()].push_back(i);
s.push(i);
}
for(int i = n; i >= 1; i--){
for(auto j : line[i]){
if(2 * j - i <= n){
debug(j, i, 2 * j - i, a[i] + a[j]);
update(1, 1, n, 2 * j - i, n, a[i] + a[j]);
}
}
for(auto [r, id] : query[i]){
debug(i, r, id, get(1, 1, n, i, r));
ans[id] = get(1, 1, n, i, r);
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
if (fopen("Kazuki.INP", "r")) {
freopen("Kazuki.INP", "r", stdin);
freopen("Kazuki.OUT", "w", stdout);
}
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
