#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
const int MAX = 500010;
int n, q;
int arr[MAX];
int ql[MAX], qr[MAX];
vector<pii> pairs;
vector<vi> ev;
// modify : time, 2, suf. pos, val
// query : time = L, 1, R, id
int res[MAX];
#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]
struct Node{
int sl, sr;
int Max;
int change;
int tag;
};
Node st[4*MAX];
void build(int cidx, int cl, int cr){
V.sl = cl;
V.sr = cr;
V.change = 0;
V.tag = 0;
if(cl < cr){
int mid = (cl + cr) / 2;
build(cidx*2, cl, mid);
build(cidx*2+1, mid+1, cr);
V.Max = max(LC.Max, RC.Max);
}
else{
V.Max = arr[cl];
}
}
void push(int cidx){
if(V.tag == 0) return;
V.Max += V.tag;
assert(V.change != -1);
V.change += V.tag;
if(V.sl < V.sr){
LC.tag += V.tag;
RC.tag += V.tag;
}
V.tag = 0;
}
void pull(int cidx){
push(cidx);
if(V.sl < V.sr){
push(cidx*2);
push(cidx*2+1);
V.Max = max(LC.Max, RC.Max);
if(LC.change == RC.change) V.change = LC.change;
else V.change = -1;
}
}
void modify(int cidx, int ml, int mr, int val){
if(mr < V.sl or V.sr < ml) return;
pull(cidx);
if(ml <= V.sl and V.sr <= mr and V.change != -1){
if(V.change < val) V.tag += val - V.change;
return;
}
modify(cidx*2, ml, mr, val);
modify(cidx*2+1, ml, mr, val);
pull(cidx);
}
int query(int cidx, int ql, int qr){
if(qr < V.sl or V.sr < ql) return -INF;
pull(cidx);
if(ql <= V.sl and V.sr <= qr) return V.Max;
return max( query(cidx*2, ql, qr) , query(cidx*2 + 1, ql, qr) );
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
FOR(i, 1, n, 1){
cin>>arr[i];
}
cin>>q;
FOR(i, 1, q, 1){
cin>>ql[i]>>qr[i];
}
vi mq;
mq.pb(n);
for(int i = n-1; i >= 1; i--){
while(!mq.empty() and arr[mq.back()] < arr[i]){
pairs.eb(i, mq.back());
mq.pop_back();
}
if(!mq.empty()) pairs.eb(i, mq.back());
mq.pb(i);
}
/*
cerr<<"pairs : "<<endl;
for(pii p : pairs){
cerr<<"("<<p.F<<", "<<p.S<<") "<<endl;
}
cerr<<endl;
*/
for(pii p : pairs){
if(2 * p.S - p.F > n) continue;
ev.pb({p.F, 2, 2 * p.S - p.F, arr[p.F] + arr[p.S]});
}
FOR(i, 1, q, 1){
ev.pb({ql[i], 1, qr[i], i});
}
sort(ev.begin(), ev.end());
reverse(ev.begin(), ev.end());
build(1, 1, n);
for(vi E : ev){
int type = E[1];
if(type == 2){ // modify
int L = E[2];
int val = E[3];
modify(1, L, n, val);
//cerr<<"modify ["<<L<<", "<<n<<"] val = "<<val<<endl;
}
else if(type == 1){ // query
int L = E[0];
int R = E[2];
int id = E[3];
res[id] = query(1, L, R);
//cerr<<"query ["<<L<<", "<<R<<"] = "<<res[id]<<endl;
}
}
FOR(i, 1, q, 1){
cout<<res[i]<<'\n';
}
return 0;
}
