#include <bits/stdc++.h>
#define rep(i, min, max) for(int i = (min); i <= (max); ++i)
#define nrep(i, max, min) for(int i = (max); i >= (min); --i)
#define reads(str) (scanf("%s", str + 1), strlen(str + 1))
#define case() int Ts = read(); rep(T, 1, Ts)
#define putf(flag) puts((flag) ? "YES" : "NO")
#define put(x) printf("%d ", x)
#define putl(x) printf("%lld ", x)
#define endl() putchar('\n')
using namespace std;

typedef long long ll;
inline int read()
{
    int now=0; bool nev=false; char c=getchar();
    while(c<'0' || c>'9') { if(c=='-') nev=true; c=getchar(); }
    while(c>='0' && c<='9') { now=(now<<1)+(now<<3)+(c&15); c=getchar(); }
    return nev?-now:now;
}

const int N = 2e6 + 10;
int n;

namespace SEG {
    #define ls (x << 1)
    #define rs (x << 1 | 1) 
    struct node {
        ll mx, hmx, tag, tagmx;
    } s[N];
    inline void maketag(int x, ll tag, ll tagmx) {
        s[x].tagmx = max(s[x].tagmx, s[x].tag + tagmx);
        s[x].hmx = max(s[x].hmx, s[x].mx + tagmx);
        s[x].tag += tag;
        s[x].mx += tag;
    }
    inline void pushdown(int x) {
        maketag(ls, s[x].tag, s[x].tagmx);
        maketag(rs, s[x].tag, s[x].tagmx);
        s[x].tag = s[x].tagmx = 0;
    }
    inline void pushup(int x) {
        s[x].mx = max(s[ls].mx, s[rs].mx);
        s[x].hmx = max(s[ls].hmx, s[rs].hmx);
    }
    void update(int x, int l, int r, ll v, int ql = 1, int qr = n) {
        if(r < ql || qr < l) return;
        // print(ql, qr, v);
        if(l <= ql && qr <= r) return maketag(x, v, max(0ll, v));
        pushdown(x);
        int mid = (ql + qr) >> 1;
        update(ls, l, r, v, ql, mid);
        update(rs, l, r, v, mid + 1, qr);
        pushup(x);
    }
    ll query(int x, int l, int r, int ql = 1, int qr = n) {
        if(r < ql || qr < l) return 0;
        if(l <= ql && qr <= r) return s[x].hmx;
        pushdown(x);
        int mid = (ql + qr) >> 1;
        return max(query(ls, l, r, ql, mid), query(rs, l, r, mid + 1, qr));
    }
}

ll a[N], ans[N];
stack<int> st;
vector<pair<int, int>> que[N], upd[N];

int main() {
    n = read();
    rep(i, 1, n) a[i] = read(), SEG :: update(1, i, i, a[i]);
    int q = read();
    rep(i, 1, q) { int l = read(), r = read(); que[l].push_back({r, i}); }
    rep(i, 1, n) {
        while(!st.empty()) {
            upd[st.top()].push_back({i * 2 - st.top(), a[i] + a[st.top()]});
            // print(i, st.top());
            if(a[st.top()] > a[i]) break;
            st.pop();
        }
        st.push(i);
    }
    nrep(l, n, 1) {
        for(auto &p : upd[l]) {
            SEG :: update(1, p.first, n, p.second);
            SEG :: update(1, p.first, n, -p.second);
        }
        for(auto &p : que[l]) {
            ans[p.second] = SEG :: query(1, l, p.first);
        }
    }
    rep(i, 1, q) putl(ans[i]), endl();
}