#include <bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int tole[500005],tori[500005],maxsuff[500005];
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(int c=le;c<=ri;c++)
{
int st = tole[c];
if(st < le)
continue;
if(c + (c-st) <= ri)
rez = max(rez, a[st] + a[c] + maxsuff[c + (c-st)]);
}
for(int st=le;st<=ri;st++)
{
int c = tori[st];
if(c > ri)
continue;
if(c + (c-st) <= ri)
rez = max(rez, a[st] + a[c] + maxsuff[c + (c-st)]);
}
return rez;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
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;
}
}
}
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
*/
