/// no sound bitch
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,ll>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)5e5 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;
void InputFile()
{
//freopen("scrivener.inp","r",stdin);
//freopen("scrivener.out","w",stdout);
//freopen("test.out","r",stdin);
}
void FastInput()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
struct TQuery
{
int lf,rt,id;
};
vector<TQuery> save_query;
bool FQ(TQuery x,TQuery y)
{
return x.lf > y.lf;
}
int n;
int q;
int a[maxN];
vector<pii> req;
int res[maxN];
struct Node
{
int max_a;
int lazy;
int val;
};
Node ST[4*maxN];
void Build(int id,int l,int r)
{
if(l == r)
{
ST[id].max_a = ST[id].val = a[l];
ST[id].lazy = 0;
return;
}
int mid = (l + r) / 2;
Build(id * 2,l,mid);
Build(id * 2 + 1,mid + 1,r);
ST[id].max_a = ST[id].val = max(ST[id*2].max_a,ST[id*2+1].max_a);
ST[id].lazy = 0;
}
void Down(int id)
{
if(!ST[id].lazy) return;
ST[id*2].val = max(ST[id*2].val,ST[id*2].max_a + ST[id].lazy);
ST[id*2].lazy = max(ST[id*2].lazy,ST[id].lazy);
ST[id*2+1].val = max(ST[id*2+1].val,ST[id*2+1].max_a + ST[id].lazy);
ST[id*2+1].lazy = max(ST[id*2+1].lazy,ST[id].lazy);
ST[id].lazy = 0;
}
void Update(int id,int l,int r,int u,int v,int n_val)
{
if(v < l || u > r) return;
if(u <= l && r <= v)
{
ST[id].val = max(ST[id].val,ST[id].max_a + n_val);
ST[id].lazy = max(ST[id].lazy,n_val);
return;
}
Down(id);
int mid = (l + r) / 2;
Update(id * 2,l,mid,u,v,n_val);
Update(id * 2 + 1,mid + 1,r,u,v,n_val);
ST[id].val = max(ST[id*2].val,ST[id*2+1].val);
}
int Get(int id,int l,int r,int u,int v)
{
if(v < l || u > r) return -infty;
if(u <= l && r <= v)
{
return ST[id].val;
}
Down(id);
int mid = (l + r) / 2;
return max(Get(id * 2,l,mid,u,v),Get(id * 2 + 1,mid + 1,r,u,v));
}
void Read()
{
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
cin >> q;
for(int i = 1;i <= q;i++)
{
int l,r;
cin >> l >> r;
save_query.push_back({l,r,i});
}
}
void Solve()
{
//cout <<"dark";return;
vector<int> vc;
for(int i = n;i >= 1;i--)
{
if(vc.empty()) vc.push_back(i);
else
{
while(!vc.empty() && a[vc.back()] < a[i])
{
req.push_back({i,vc.back()});
vc.pop_back();
}
if(!vc.empty()) req.push_back({i,vc.back()});
vc.push_back(i);
}
}
sort(req.begin(),req.end(),greater<pii>());
sort(save_query.begin(),save_query.end(),FQ);
/*for(pii tmp : req)
{
cout <<'*'<<' '<< tmp.fi <<' '<< tmp.se <<'\n';
}
return;*/
Build(1,1,n);
int pt = 0;
for(TQuery tmp : save_query)
{
while(pt < req.size() && req[pt].fi >= tmp.lf)
{
if(2 * req[pt].se - req[pt].fi <= n)
{
Update(1,1,n,2*req[pt].se-req[pt].fi,n,a[req[pt].fi]+a[req[pt].se]);
}
pt++;
}
res[tmp.id] = Get(1,1,n,tmp.lf+2,tmp.rt);
}
for(int i = 1;i <= q;i++)
{
cout << res[i] <<'\n';
}
}
void Debug()
{
}
int32_t main()
{
FastInput();
//InputFile();
//int sub_type;
//cin >> sub_type;
//Sieve();
//Prepare();
int test;
//cin >> test;
test = 1;
while(test--)
//for(int prc = 1; prc <= test; prc++)
{
Read();
Solve();
//Debug();
}
}
