// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
const int N = 5e5+5;
const int BIG = 2e9;
int n, q, a[N];
int sgt[N * 4], pos[N * 4];
int comb(int i, int j) {
return a[i] >= a[j] ? i : j;
}
void build(int id, int lb, int rb) {
if (lb ^ rb) {
int mb = (lb + rb) >> 1;
build(id*2, lb, mb);
build(id*2+1, mb+1, rb);
sgt[id] = max(sgt[id*2], sgt[id*2+1]);
pos[id] = comb(pos[id*2], pos[id*2+1]);
}
else {
sgt[id] = a[lb];
pos[id] = lb;
}
}
int query(int id, int lb, int rb, int l, int r) {
if (l <= lb && rb <= r) return sgt[id];
if (rb < l || lb > r) return -BIG;
int mb = (lb + rb) >> 1;
return max(query(id*2, lb, mb, l, r), query(id*2+1, mb+1, rb, l, r));
}
int findpos(int id, int lb, int rb, int l, int r) {
if (l <= lb && rb <= r) return pos[id];
if (rb < l || lb > r) return 0;
int mb = (lb + rb) >> 1;
return comb(findpos(id*2, lb, mb, l, r), findpos(id*2+1, mb+1, rb, l, r));
}
int solve(int l, int r) {
if ((r-l+1) < 3) return 0;
int pos_max = findpos(1, 1, n, l+1, r-1);
int ans = max(solve(l, pos_max), solve(pos_max, r));
if (r - pos_max < pos_max - l) {
for(int d = 1; d <= r - pos_max; ++d) {
int k = pos_max+d;
ans = max(ans, a[k] + a[pos_max] + query(1, 1, n, pos_max-d, pos_max-1));
}
}
else {
for(int d = 1; d <= pos_max - l; ++d) {
int k = pos_max-d;
ans = max(ans, a[k] + a[pos_max] + query(1, 1, n, pos_max+d, r));
}
}
// cout << l << " " << r << " " << ans << "\n";
return ans;
}
int main() {
cin >> n;
foru(i, 1, n) cin >> a[i];
cin >> q;
foru(i, 1, q) {
int l, r;
cin >> l >> r;
}
build(1, 1, n);
cout << solve(1, n);
return 0;
}
