/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define F(i,a,b) for (ll i=a;i<=b;i++)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=5e5+40;
const ll mod=1000003 ;
const ll base=3e18;
/// you will be the best but now you just are trash
/// goal 1/7
ll n;
ll a[maxn];
vector<pll> adj[maxn];
vector<ll> adj1[maxn];
ll res[maxn];
struct tk
{
ll la=0;
ll val=0;
ll mx=0;
};
tk st[4*maxn];
tk mer(tk a,tk b)
{
a.la=0;
b.la=0;
if (a.mx==-base) return b;
if (b.mx==-base) return a;
tk c;
c.val=max(a.val,b.val);
c.mx=max(a.mx,b.mx);
return c ;
}
void build(ll id,ll left,ll right)
{
if (left==right)
{
st[id].mx=a[left];
st[id].val=a[left];
return ;
}
ll mid=(left+right)/2;
build(id*2,left,mid);
build(id*2+1,mid+1,right);
st[id]=mer(st[id*2],st[id*2+1]);
}
void dosth(ll id,ll left,ll right)
{
if (st[id].la==0) return ;
st[id*2].la=max(st[id*2].la,st[id].la);
st[id*2+1].la=max(st[id*2+1].la,st[id].la);
st[id*2].mx=max(st[id*2].mx,st[id].la+st[id*2].val);
st[id*2+1].mx=max(st[id*2+1].mx,st[id].la+st[id*2+1].val);
st[id].la=0;
}
void update(ll id,ll left,ll right,ll x,ll y,ll diff)
{
if (x>right||y<left) return ;
if (x<=left&&y>=right)
{
st[id].la=max(st[id].la,diff);
st[id].mx=max(st[id].mx,st[id].val+diff);
return ;
}
dosth(id,left,right);
ll mid=(left+right)/2;
update(id*2,left,mid,x,y,diff);
update(id*2+1,mid+1,right,x,y,diff);
st[id]=mer(st[id*2],st[id*2+1]);
}
tk get(ll id,ll left,ll right,ll x,ll y)
{
tk a;
a.mx=-base;
if (x>right||y<left) return a;
if (x<=left&&y>=right) return st[id];
dosth(id,left,right);
ll mid=(left+right)/2;
return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
cin>> n;
for (int i=1;i<=n;i++)
{
cin>> a[i];
}
stack<ll> st;
for (int i=n;i>=1;i--)
{
while (!st.empty())
{
auto p=st.top();
adj1[i].pb(p);
if (a[i]<a[p]) break;
else st.pop();
}
st.push(i);
}
build(1,1,n);
ll q;
cin>> q;
for (int i=1;i<=q;i++)
{
ll x , y;
cin>>x>> y;
adj[x].pb(make_pair(y,i));
}
for (int i=n;i>=1;i--)
{
for (auto to:adj1[i])
{
// cout <<i<<" "<<to<<" chk"<<endl;
ll nxt=2*to-i;
update(1,1,n,nxt,n,a[i]+a[to]);
}
for (auto to:adj[i])
{
res[to.ss]=get(1,1,n,i,to.ff).mx;
}
}
for (int i=1;i<=q;i++)
{
cout <<res[i]<<endl;
}
}
