#include <bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int tole[500005],tori[500005],maxsuff[500005];
vector<pair<pair<int,int>,int>> intervals;
int solve(int le, int ri)
{
maxsuff[ri+1] = 0;
for(int i=ri;i>=le;i--)
{
maxsuff[i] = max(maxsuff[i+1], a[i]);
}
int rez=0;
for(auto [x,val]:intervals)
{
if(le <= x.first && x.second <= ri)
rez = max(rez, val + maxsuff[x.second]);
}
return rez;
}
void calc_toletori()
{
deque<int> dq;
for(int i=1;i<=n;i++)
{
while(!dq.empty() && a[i] > a[dq.back()])
dq.pop_back();
if(dq.empty())
tole[i] = 0;
else
tole[i] = dq.back();
dq.push_back(i);
}
dq.clear();
for(int i=n;i>0;i--)
{
while(!dq.empty() && a[i] > a[dq.back()])
dq.pop_back();
if(dq.empty())
tori[i] = n+1;
else
tori[i] = dq.back();
dq.push_back(i);
}
}
void get_intervals()
{
for(int c=1;c<=n;c++)
{
int st = tole[c];
if(st==0)
continue;
intervals.push_back({{st, c + (c-st)}, a[c]+a[st]});
}
for(int st=1;st<=n;st++)
{
int c = tori[st];
if(c==n+1)
continue;
intervals.push_back({{st, c + (c-st)}, a[c]+a[st]});
}
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
calc_toletori();
get_intervals();
int q;
cin>>q;
while(q--)
{
int le,ri;
cin>>le>>ri;
cout<<solve(le,ri)<<"\n";
}
return 0;
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
tori[i] = prima pozitie x din dreapta lui i cu a[x] >= a[i]
tole[i] = prima pozitie x din stanga lui i cu a[x] >= a[i]
daca ne fixam capatu stanga in le, centru o sa fie in intervalu le+1..tori[le]
daca ne fixam centru in c, capatu stanga o sa fie in tole[c]..c-1
*/
