#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()
{
for(int i=1;i<=n;i++)
{
tole[i] = 0;
for(int u=i-1;u>=1;u--)
{
if(a[u] >= a[i])
{
tole[i] = u;
break;
}
}
tori[i] = n+1;
for(int u=i+1;u<=n;u++)
{
if(a[u] >= a[i])
{
tori[i] = u;
break;
}
}
}
}
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
*/
