/*#include <bits/stdc++.h>
using namespace std;
int segment[200001], n, arr[50001], ret;
int make(int node, int start, int End)
{
if(start==End){
return segment[node]=arr[start];
}
int mid=(start+End)/2;
int ri=make(node*2, start, mid);
int le=make(node*2+1, mid+1, End);
segment[node]=max(ri, le);
return segment[node];
}
int result(int node, int start, int End, int l, int r)
{
if(End<l||start>r)return 0;
if(l<=start&&End<=r)return segment[node];
int mid=(start+End)/2;
int ri=result(node*2, start, mid, l, r);
int le=result(node*2+1, mid+1, End, l, r);
ret=max(ri, le);
return ret;
}
int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++)
scanf("%d", &arr[i]);
make(1, 0, n-1);
int m;
scanf("%d", &m);
int a, b;
for(int i=1;i<=m;i++)
{
scanf("%d %d", &a, &b);
printf("%d ", result(1, 0, n-1, a-1, b-1));
}
}*/
/*
#include <bits/stdc++.h>
using namespace std;
int maxsegment[200001], arr[50001], n, minsegment[200001];
void make(int node, int start, int End)
{
if(start==End)
{
maxsegment[node]=minsegment[node]=arr[start];
return ;
}
int mid=(start+End)/2;
make(node*2, start, mid);
make(node*2+1, mid+1, End);
maxsegment[node]=max(maxsegment[node*2], maxsegment[node*2+1]);
minsegment[node]=min(minsegment[node*2], minsegment[node*2+1]);
}
int maxres(int node, int start, int End, int l, int r)
{
if(start>=l&&End<=r)return maxsegment[node];
if(End<l||start>r)return 0;
int mid=(start+End)/2;
int res1=maxres(node*2, start, mid, l, r);
int res2=maxres(node*2+1, mid+1, End, l, r);
return max(res1, res2);
}
int minres(int node, int start, int End, int l, int r)
{
if(start>=l&&End<=r)return minsegment[node];
if(End<l||start>r)return 2147483647;
int mid=(start+End)/2;
return min(minres(node*2, start, mid, l, r), minres(node*2+1, mid+1, End, l, r));
}
int main()
{
int m;
scanf("%d %d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%d", &arr[i]);
make(1, 1, n);
int a, b;
//printf("%d %d", maxsegment[1], minsegment[1]);
for(int i=1;i<=m;i++)
{
scanf("%d %d", &a, &b);
printf("%d\n", maxres(1, 1, n, a, b)-minres(1, 1, n, a, b));
}
}*/
#include <bits/stdc++.h>
using namespace std;
int segment[200001], n, m, arr[50001];
int make(int node, int start, int End)
{
if(start==End)return segment[node]=arr[start];
int mid=(start+End)/2;
int l=mid, r=mid+1, le=l, ri=r;
for(int i=mid-1;i>=start;i--)
{
l+=arr[i];
le=max(l, le);
}
for(int i=mid+2;i<=End;i++)
{
r+=arr[i];
ri=max(ri, r);
}
return segment[node]=max(le+ri, max(make(node*2, start, mid), make(node*2+1, mid+1, End)));
}
int res(int node, int start, int End, int lef, int rig)
{
if(start>=lef&&End<=rig)return segment[node];
if(End<lef||start>rig)return -987654321;
int mid=(start+End)/2;
int l=mid, r=mid+1, le=l, ri=r;
for(int i=mid-1;i>=max(start, lef);i--)
{
l+=arr[i];
le=max(l, le);
}
for(int i=mid+2;i<=min(End, rig);i++)
{
r+=arr[i];
ri=max(ri, r);
}
return max(max(le+ri, res(node*2, start, mid, lef, rig)), res(node*2+1, mid+1, End, lef, rig));
}
int main()
{
scanf("%d", &n);
for(int i=1;i<=n;i++)scanf("%d", &arr[i]);
make(1, 1, n);
printf("%d", segment[1]);
scanf("%d", &m);
int a, b;
for(int i=1;i<=m;i++)
{
scanf("%d %d", &a, &b);
printf("%d\n", res(1, 1, n, a, b));
}
}