#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 val;
ll Min1;
ll Min2;
int lazy;
Node ()
{
x = 0 , val = 0 , lazy = 0;
Min1 = 0;
Min2 = inf;
}
Node operator + (Node & other)
{
Node ans;
if(x + val >= other.x + other.val)
{
ans.x = x;
ans.val = val;
}
else
{
ans.x = other.x;
ans.val = other.val;
}
if(Min1 < other.Min1)
{
ans.Min1 = Min1;
ans.Min2 = min(other.Min1 , Min2);
}
else if(Min1 > other.Min1)
{
ans.Min1 = other.Min1;
ans.Min2 = min(Min1 , other.Min2);
}
else
{
ans.Min1 = Min1;
ans.Min2 = min(other.Min2 , Min2);
}
return ans;
}
};
Node st[4 * maxn];
void build(int i ,int l , int r)
{
if(l == r)
{
st[i].x = 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 ApplyMax(int i , int val ,int Max)
{
if(val > st[i].Min1)
{
st[i].Min1 = val;
}
else return;
if(st[i].Min2 == inf) st[i].val = val;
else st[i].val = Max;
}
void Push(int i)
{
ApplyMax(i * 2 , st[i].Min1 , st[i].val);
ApplyMax(i * 2 + 1, st[i].Min1 , st[i].val);
}
void update(int i ,int l ,int r, int u , int v ,ll val)
{
if(u > r || v < l || val <= st[i].Min1) return;
if(u <= l && r <= v && val < st[i].Min2)
{
ApplyMax(i , val , st[i].val);
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].x + st[i].val;
}
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 ""
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int tc; tc = 1;
while(tc--) solve();
//execute;
}
