#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <complex>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <string>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define all(x) (x).begin(), (x).end()
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
#ifdef KAZAR
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
#define eprintf(...) 0
#endif
using namespace std;
template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef pair<int, int> ii;
const int inf = 1e9 + 143;
const ll longinf = 1e18 + 143;
inline int read(){int x;scanf(" %d",&x);return x;}
const int N = 50500;
const int M = 1e6 + 100;
const int BLOCK = 400;
int a[N];
int ps[N];
int l[M], r[M];
int ans[M];
vector<int> q[N / BLOCK + 5];
bool byr(const int &a,const int &b){
return r[a] < r[b];
}
int main(){
#ifdef KAZAR
freopen("f.input","r",stdin);
freopen("f.output","w",stdout);
freopen("error","w",stderr);
#endif
int n = read();
for(int i = 0; i < n; i++){
a[i] = read();
ps[i] = ps[i - 1] + a[i];
}
int m = read();
for(int i = 0; i < m; i++){
l[i] = read() - 1;
r[i] = read() - 1;
ans[i] = -inf;
q[l[i] / BLOCK].push_back(i);
}
for(int it = 0; it * BLOCK < n; it++){
int from = it * BLOCK;
int to = from + BLOCK - 1;
sort(all(q[it]), byr);
int ptr = to + 1, max_ps = -inf, min_ps = ps[to], max_sum = -inf;
foreach(qit, q[it]){
int id = *qit;
int r = ::r[id];
int l = ::l[id];
if(r <= to){
int lval = ps[l - 1];
for(int j = l; j <= r; j++){
umax(ans[id], ps[j] - lval);
umin(lval, ps[j]);
}
}else{
while(ptr <= r){
umax(max_sum, ps[ptr] - min_ps);
umax(max_ps, ps[ptr]);
umin(min_ps, ps[ptr]);
ptr++;
}
int lval = ps[l - 1];
for(int i = l; i <= to; i++){
umax(ans[id], ps[i] - lval);
umin(lval, ps[i]);
}
umax(ans[id], max_ps - lval);
umax(ans[id], max_sum);
}
}
}
for(int i = 0; i < m; i++){
printf("%d\n", ans[i]);
}
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxjb21wbGV4PgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzZXQ+CgojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwgKHgpLmVuZCgpCiNkZWZpbmUgdHlwZSh4KSBfX3R5cGVvZigoeCkuYmVnaW4oKSkKI2RlZmluZSBmb3JlYWNoKGl0LCB4KSBmb3IodHlwZSh4KSBpdCA9ICh4KS5iZWdpbigpOyBpdCAhPSAoeCkuZW5kKCk7IGl0KyspCgojaWZkZWYgS0FaQVIKICAgICNkZWZpbmUgZXByaW50ZiguLi4pIGZwcmludGYoc3RkZXJyLF9fVkFfQVJHU19fKQojZWxzZQogICAgI2RlZmluZSBlcHJpbnRmKC4uLikgMAojZW5kaWYKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgdm9pZCB1bWF4KFQgJmEsVCBiKXtpZihhPGIpIGEgPSBiIDsgfQp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgdm9pZCB1bWluKFQgJmEsVCBiKXtpZihhPmIpIGEgPSBiIDsgfQp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgVCBhYnMoVCBhKXtyZXR1cm4gYT4wID8gYSA6IC1hO30KdGVtcGxhdGU8Y2xhc3MgVD4gaW5saW5lIFQgZ2NkKFQgYSxUIGIpe3JldHVybiBfX2djZChhLCBiKTt9CnRlbXBsYXRlPGNsYXNzIFQ+IGlubGluZSBUIGxjbShUIGEsVCBiKXtyZXR1cm4gYS9nY2QoYSxiKSpiO30KCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IGlpOwoKY29uc3QgaW50IGluZiA9IDFlOSArIDE0MzsKY29uc3QgbGwgbG9uZ2luZiA9IDFlMTggKyAxNDM7CgppbmxpbmUgaW50IHJlYWQoKXtpbnQgeDtzY2FuZigiICVkIiwmeCk7cmV0dXJuIHg7fQoKY29uc3QgaW50IE4gPSA1MDUwMDsKY29uc3QgaW50IE0gPSAxZTYgKyAxMDA7CmNvbnN0IGludCBCTE9DSyA9IDQwMDsKCmludCBhW05dOwppbnQgcHNbTl07CgppbnQgbFtNXSwgcltNXTsKaW50IGFuc1tNXTsKCnZlY3RvcjxpbnQ+IHFbTiAvIEJMT0NLICsgNV07Cgpib29sIGJ5cihjb25zdCBpbnQgJmEsY29uc3QgaW50ICZiKXsKICAgIHJldHVybiByW2FdIDwgcltiXTsKfQoKaW50IG1haW4oKXsKCiNpZmRlZiBLQVpBUgogICAgZnJlb3BlbigiZi5pbnB1dCIsInIiLHN0ZGluKTsKICAgIGZyZW9wZW4oImYub3V0cHV0IiwidyIsc3Rkb3V0KTsKICAgIGZyZW9wZW4oImVycm9yIiwidyIsc3RkZXJyKTsKI2VuZGlmCgogICAgaW50IG4gPSByZWFkKCk7CgogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgYVtpXSA9IHJlYWQoKTsKICAgICAgICBwc1tpXSA9IHBzW2kgLSAxXSArIGFbaV07CiAgICB9CgogICAgaW50IG0gPSByZWFkKCk7CgogICAgZm9yKGludCBpID0gMDsgaSA8IG07IGkrKyl7CiAgICAgICAgbFtpXSA9IHJlYWQoKSAtIDE7CiAgICAgICAgcltpXSA9IHJlYWQoKSAtIDE7CiAgICAgICAgYW5zW2ldID0gLWluZjsKICAgICAgICBxW2xbaV0gLyBCTE9DS10ucHVzaF9iYWNrKGkpOwogICAgfQoKICAgIGZvcihpbnQgaXQgPSAwOyBpdCAqIEJMT0NLIDwgbjsgaXQrKyl7CiAgICAgICAgaW50IGZyb20gPSBpdCAqIEJMT0NLOwogICAgICAgIGludCB0byA9IGZyb20gKyBCTE9DSyAtIDE7CiAgICAgICAgc29ydChhbGwocVtpdF0pLCBieXIpOwogICAgICAgIGludCBwdHIgPSB0byArIDEsIG1heF9wcyA9IC1pbmYsIG1pbl9wcyA9IHBzW3RvXSwgbWF4X3N1bSA9IC1pbmY7CiAgICAgICAgZm9yZWFjaChxaXQsIHFbaXRdKXsKICAgICAgICAgICAgaW50IGlkID0gKnFpdDsKICAgICAgICAgICAgaW50IHIgPSA6OnJbaWRdOwogICAgICAgICAgICBpbnQgbCA9IDo6bFtpZF07CiAgICAgICAgICAgIGlmKHIgPD0gdG8pewogICAgICAgICAgICAgICAgaW50IGx2YWwgPSBwc1tsIC0gMV07CiAgICAgICAgICAgICAgICBmb3IoaW50IGogPSBsOyBqIDw9IHI7IGorKyl7CiAgICAgICAgICAgICAgICAgICAgdW1heChhbnNbaWRdLCBwc1tqXSAtIGx2YWwpOwogICAgICAgICAgICAgICAgICAgIHVtaW4obHZhbCwgcHNbal0pOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgICAgIHdoaWxlKHB0ciA8PSByKXsKICAgICAgICAgICAgICAgICAgICB1bWF4KG1heF9zdW0sIHBzW3B0cl0gLSBtaW5fcHMpOwogICAgICAgICAgICAgICAgICAgIHVtYXgobWF4X3BzLCBwc1twdHJdKTsKICAgICAgICAgICAgICAgICAgICB1bWluKG1pbl9wcywgcHNbcHRyXSk7CiAgICAgICAgICAgICAgICAgICAgcHRyKys7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpbnQgbHZhbCA9IHBzW2wgLSAxXTsKICAgICAgICAgICAgICAgIGZvcihpbnQgaSA9IGw7IGkgPD0gdG87IGkrKyl7CiAgICAgICAgICAgICAgICAgICAgdW1heChhbnNbaWRdLCBwc1tpXSAtIGx2YWwpOwogICAgICAgICAgICAgICAgICAgIHVtaW4obHZhbCwgcHNbaV0pOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgdW1heChhbnNbaWRdLCBtYXhfcHMgLSBsdmFsKTsKICAgICAgICAgICAgICAgIHVtYXgoYW5zW2lkXSwgbWF4X3N1bSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgZm9yKGludCBpID0gMDsgaSA8IG07IGkrKyl7CiAgICAgICAgcHJpbnRmKCIlZFxuIiwgYW5zW2ldKTsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=