#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
using namespace std;
template <typename T> void debug (T x) {
cerr<<x<<'\n';
}
template <typename T> void debuglen (T x) {
cerr<<x<<' ';
}
template <typename T,typename...Args> void debug (T x,Args...args) {
cerr<<x<<' ';
debug(args...);
}
template <typename T> void debug (T*lt,T*rt) {
ll len=rt-lt;
for (ll i=0;i<len;i++) {
debuglen(*(lt+i));
}
cerr<<'\n';
}
inline ll read () {
char x=getchar();
ll ans=0,f=1;
while (x<'0'||x>'9') {
if (x=='-') {
f=-1;
}
x=getchar();
}
while (x>='0'&&x<='9') {
ans=(ans<<1)+(ans<<3);
ans+=(x^'0');
x=getchar();
}
return ans*f;
}
void print (ll x) {
if (x<0) {
x=-x;
putchar('-');
}
if (x>=10) {
print(x/10);
}
putchar(x%10+'0');
}
}
using namespace io;
const ll N=5e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
struct node {
ll op,l,r,pos;
};
ll n,a[N],q,L[N],R[N],ans[N];
ll st[N],top;
vector<node> num;
struct info {
ll val,mx;
inline void clear () {
val=0;
}
};
struct Tag {
ll val;
inline void clear () {
val=0;
}
};
inline info operator + (info a,info b) {
a.val=max(a.val,b.val);
a.mx=max(a.mx,b.mx);
return a;
}
inline info operator + (info a,ll b) {
a.val=max(a.val,b+a.mx);
return a;
}
inline info operator + (info a,Tag b) {
a.val=max(a.val,a.mx+b.val);
return a;
}
inline Tag operator + (Tag a,Tag b) {
a.val=max(a.val,b.val);
return a;
}
inline Tag operator + (Tag a,ll b) {
a.val=max(a.val,b);
return a;
}
struct Segtree {
info t[N<<2];
Tag lt[N<<2];
inline void push_up (ll pos) {
t[pos]=t[pos<<1]+t[pos<<1|1];
}
inline void push_down (ll pos) {
t[pos<<1]=t[pos<<1]+lt[pos];
t[pos<<1|1]=t[pos<<1|1]+lt[pos];
lt[pos<<1]=lt[pos<<1]+lt[pos];
lt[pos<<1|1]=lt[pos<<1|1]+lt[pos];
lt[pos].clear();
}
void build (ll pos,ll l,ll r) {
if (l==r) {
t[pos].mx=t[pos].val=a[l];
return ;
}
ll mid=(l+r)>>1;
build(pos<<1,l,mid);
build(pos<<1|1,mid+1,r);
push_up(pos);
}
void add (ll pos,ll l,ll r,ll L,ll R,ll val) {
if (L<=l&&r<=R) {
t[pos]=t[pos]+val;
lt[pos]=lt[pos]+val;
return ;
}
push_down(pos);
ll mid=(l+r)>>1;
if (L<=mid) {
add(pos<<1,l,mid,L,R,val);
}
if (R>mid) {
add(pos<<1|1,mid+1,r,L,R,val);
}
push_up(pos);
}
info query (ll pos,ll l,ll r,ll L,ll R) {
if (L<=l&&r<=R) {
return t[pos];
}
push_down(pos);
ll mid=(l+r)>>1;
info cnt;
cnt.clear();
if (L<=mid) {
cnt=cnt+query(pos<<1,l,mid,L,R);
}
if (R>mid) {
cnt=cnt+query(pos<<1|1,mid+1,r,L,R);
}
return cnt;
}
} tr;
inline void solve () {
n=read();
for (ll i=1;i<=n;i++) {
a[i]=read();
}
for (ll i=1;i<=n;i++) {
while (top&&a[st[top]]<a[i]) {
top--;
}
L[i]=st[top];
st[++top]=i;
}
top=0;
for (ll i=n;i>=1;i--) {
while (top&&a[st[top]]<a[i]) {
top--;
}
R[i]=st[top];
st[++top]=i;
}
for (ll i=1;i<=n;i++) {
if (L[i]) {
num.push_back({1,L[i],i,0});
}
if (R[i]) {
num.push_back({1,i,R[i],0});
}
}
tr.build(1,1,n);
q=read();
for (ll i=1;i<=q;i++) {
num.push_back({2,read(),read(),i});
}
sort(num.begin(),num.end(),[] (node a,node b) {
if (a.l==b.l) {
return a.op<b.op;
}
return a.l>b.l;
});
for (auto [op,l,r,pos] : num) {
if (op==1) {
ll rt=(r<<1)-l;
if (rt<=n) {
tr.add(1,1,n,rt,n,a[l]+a[r]);
}
}
else {
ans[pos]=tr.query(1,1,n,l,r).val;
}
}
for (ll i=1;i<=q;i++) {
print(ans[i]);
puts("");
}
}
int main () {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll T=1;
// T=read();
while (T--) {
solve();
}
return 0;
}
