#include <bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int tole[500005],tori[500005];
vector<pair<pair<int,int>,int>> intervals;
vector<pair<int,int>> withri[500005];
const int BUC = 10;
const int CNTB = 1005;
int prec[CNTB][CNTB];
int maxsuff[500005];
int solve(int le, int ri)
{
maxsuff[ri+1] = 0;
int rez = prec[le/BUC][ri/BUC];
if(le/BUC == ri/BUC)
{
for(int i=ri;i>=le;i--)
{
maxsuff[i] = max(maxsuff[i+1], a[i]);
}
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)]);
}
}
else
{
for(int i=ri;i>=le;i--)
{
maxsuff[i] = max(maxsuff[i+1], a[i]);
}
for(auto [x,val]:intervals)
{
if((le <= x.first && x.first < (le/BUC + 1)*BUC && x.second <= ri) || (le <= x.first && (ri/BUC)*BUC <= x.second && 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]});
}
}
void precalc_sqrt()
{
for(int ri=0;ri<=n/BUC;ri++)
{
int suff=0;
for(int u=ri*BUC-1;u>0;u--)
{
suff = max(suff, a[u]);
for(auto [ile,ival]:withri[u])
prec[ile/BUC + 1][ri] = max(prec[ile/BUC + 1][ri], suff + ival);
}
for(int le=ri-1;le>=0;le--)
prec[le][ri] = max(prec[le][ri], prec[le+1][ri]);
}
}
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();
for(auto [x,val]:intervals)
withri[x.second].push_back({x.first,val});
precalc_sqrt();
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
*/
