#include<bits/stdc++.h>
using namespace std;
// define
#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right
//constant
const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
int dx[] = {0 , -1 , 0 , 1};
int dy[] = {-1 , 0 , 1 , 0};
template<typename T> bool maximize(T &a, const T &b)
{
if(a < b) {a = b; return 1;}
return 0;
}
template<typename T> bool minimize(T &a, const T &b)
{
if(a > b) {a = b; return 1;}
return 0;
}
inline void Plus(ll & a ,ll b)
{
b %= mod;
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return;
}
inline void Mul(ll & a, ll b)
{
a %= mod; b %= mod;
a *= b;
a %= mod;
return;
}
//code
const int maxn = 5e5 + 7;
int n , a[maxn] , q;
vector <ii> Q[maxn];
vector <int> pos[maxn];
int ans[maxn];
struct Node
{
ll x;
ll ans;
ll lazy;
Node ()
{
x = 0 , lazy = 0 ,ans = 0;
}
Node operator + (Node & other)
{
Node res;
res.x = max(x , other.x);
res.ans = max(ans , other.ans);
return res;
}
};
Node st[4 * maxn];
void build(int i ,int l , int r)
{
if(l == r)
{
st[i].x = a[l];
st[i].ans = a[l];
return;
}
int mid = (r + l) >> 1;
build(i * 2 , l , mid);
build(i * 2 + 1,mid + 1 , r);
st[i] = st[i * 2] + st[i * 2 + 1];
}
void Push(int i)
{
if(st[i].lazy)
{
st[i * 2].ans = max(st[i * 2].ans , st[i * 2].x + st[i].lazy);
st[i * 2 + 1].ans = max(st[i * 2 + 1].ans , st[i * 2 + 1].x + st[i].lazy);
maximize(st[i * 2].lazy , st[i].lazy);
maximize(st[i * 2 + 1].lazy , st[i].lazy);
st[i].lazy = 0;
}
}
void update(int i ,int l ,int r, int u , int v ,ll val)
{
if(u > r || v < l) return;
if(u <= l && r <= v)
{
st[i].lazy = max(st[i].lazy , val);
st[i].ans = max(st[i].ans , val + st[i].x);
return;
}
int mid = (r + l) >> 1;
Push(i);
update(i * 2 , l , mid , u , v , val);
update(i * 2 + 1, mid + 1 , r, u , v , val);
st[i] = st[i * 2] + st[i * 2 + 1];
}
ll get(int i , int l , int r, int u , int v)
{
if(u > r || v < l) return 0;
if(u <= l && r <= v)
{
return st[i].ans;
}
int mid = (r + l) >> 1;
Push(i);
return max(get(i * 2 , l , mid , u , v) , get(i * 2 + 1, mid + 1 ,r , u , v));
}
void solve(void)
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
for(int i = 1; i <= q; i++)
{
int l , r;
cin >> l >> r;
Q[l].push_back(ii(r , i));
}
stack <int> st;
for(int i = n; i >= 1; i--)
{
while(!st.empty())
{
int id = st.top();
pos[i].push_back(id);
if(a[id] > a[i]) break;
st.pop();
}
st.push(i);
}
build(1 , 1 , n);
for(int i = n ; i >= 1; i--)
{
for(int j : pos[i])
{
if(2 * j - i <= n) update(1 , 1 , n , 2 * j - i , n , a[i] + a[j]);
}
for(ii j : Q[i])
{
ans[j.se] = get(1 , 1 , n , i + 2 , j.fi);
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
/**
**/
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define task "chonqua"
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int tc; tc = 1;
while(tc--) solve();
//execute;
}
