import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class choukdi
{
int max=0;
int pref=0;
int suff=0;
int total=0;
choukdi(int a,int b,int c,int d)
{
max=a;
pref=b;
suff=c;
total=d;
}
}
class Main
{
public static void main (String[] jatin) throws IOException
{
int n;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int arr[]=new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++)
{
arr[i]=Integer.parseInt(st.nextToken());
}
int max[]=new int[4n+1];
int pref[]=new int[4n+1];
int suff[]=new int[4n+1];
int total[]=new int[4n+1];
build_tree(arr,max,pref,suff,total,0,n-1,0);
int m;
m=Integer.parseInt(br.readLine());
while(m–!=0)
{
st = new StringTokenizer(br.readLine());
int l,r;
l=Integer.parseInt(st.nextToken());
r=Integer.parseInt(st.nextToken());
l–;r–;
choukdi ans=query_max(max,pref,suff,total,0,n-1,l,r,0);
System.out.println(ans.max);
}
}
public static choukdi query_max(int max[],int pref[],int suff[],int total[],int se,int ee,int l,int r,int root)
{
// in case of complete overlap...
if(l<=se && r>=ee)
{
return new choukdi(max[root],pref[root],suff[root],total[root]);
}
// in case of no onverlap...
if(r<se || l>ee)
{
return new choukdi(-21474836,-21474836,-21474836,0);
}
// PARTIAL-OVERLAP......
choukdi left=query_max(max,pref,suff,total,se,(se+ee)/2,l,r,2*root+1);
choukdi right=query_max(max,pref,suff,total,(ee+se)/2 +1,ee,l,r,2*root+2);
choukdi ans=new choukdi(0,0,0,0);
// setting the max value of the partial-overlap...
ans.max=left.max;
if(ans.max<right.max)
{
ans.max=right.max;
}
if(ans.max<left.suff + right.pref)
{
ans.max=left.suff + right.pref;
}
//setting the value of the pref...
ans.pref=left.pref;
if(ans.pref<left.total + right.pref)
{
ans.pref=left.total + right.pref;
}
// setting the suff....
ans.suff=right.suff;
if(ans.suff<right.total + left.suff)
{
ans.suff=right.total + left.suff;
}
// setting the total....
ans.total=left.total + right.total;
return ans;
}
public static void build_tree(int arr[],int max[],int pref[],int suff[],int total[],int se,int ee,int root)
{
// handlerd the base case..i.e when it is the leaf node....
if(se==ee)
{
total[root]=arr[se];
pref[root]=arr[se];
suff[root]=arr[se];
max[root]=arr[se];
return;
}
else // case of partial overlap you can say......
{
// we need to find out the maximum sum of the case...okkey......
// calling on left...
build_tree(arr,max,pref,suff,total,se,(se+ee)/2,2*root+1);
// calling on right...
build_tree(arr,max,pref,suff,total,(se+ee)/2 +1,ee,2*root+2);
// now buildding for the root-node..
max[root]=max[2*root+1];// it is the max of the left-tree
if(max[root]<max[2*root+2])
{
max[root]=max[2*root+2];// it is the max of right-tree.
}
if(max[root]<pref[2*root+2]+suff[2*root+1])
{
max[root]=pref[2*root+2]+suff[2*root+1];
}
//nnow we need to find the max_prefix sum...
pref[root]=pref[2*root+1];
if(total[2*root+1]+pref[2*root+2]>pref[root])
{
pref[root]=total[2*root+1]+pref[2*root+2];
}
// now we need to set the suffix-sum.....
suff[root]=suff[2*root+2];
if(suff[root]<total[2*root+2] + suff[2*root +1])
{
suff[root]=total[2*root+2] + suff[2*root +1];
}
// no we need to set the total-sum...
total[root]=total[2*root+1]+total[2*root+2];
return;
}
}
}